小程序定制开发一般要多少钱,seo公司名字,新乡网站网站建设,越南外贸平台一、最大子序和
输入一个长度为 n 的整数序列#xff0c;从中找出一段长度不超过 m 的连续子序列#xff0c;使得子序列中所有数的和最大。 注意#xff1a; 子序列的长度至少是 1。
输入 第一行输入两个整数 n,m (1 ≤ n,m ≤ 300000)。 第二行输入 n 个数#xff0c;代…一、最大子序和
输入一个长度为 n 的整数序列从中找出一段长度不超过 m 的连续子序列使得子序列中所有数的和最大。 注意 子序列的长度至少是 1。
输入 第一行输入两个整数 n,m (1 ≤ n,m ≤ 300000)。 第二行输入 n 个数代表长度为 n 的整数序列。 同一行数之间用空格隔开。
输出 输出一个整数代表该序列的最大子序和。
Input 6 4 1 -3 5 1 -2 3
Output 7
解析 在长度不超过m的连续子序列找到和最大的连续子序列。 集合按照终点的不同划分划分成 n 个子集答案就是不同子集的最大值。 假如终点是 k 的连续子序列它的最大和就是 max({a[k],a[k]a[k-1],a[k]a[k-1]a[k-2],……,a[k]…a[k-m1]}); 可以发现就是 s[k]-s[k-j] 的最大值(其中1≤j≤ms[N]是前缀和); 又因为终点 k 是确定不动的这道题就转化成求在区间长度不超过 m 的 s[k-j]的最小值典型的滑动窗口问题。
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N2e610;
int n,m;
int s[N];
int q[N];
void solve()
{cinnm;for (int i1;in;i) cins[i],s[i] s[i-1];int hh0,tt1; //最开始队列不空有s[0]int anss[1];for (int i1;in;i){if (hhtti-q[hh]m) hh;ansmax(ans,s[i]-s[q[hh]]); //比较每个子集更新答案while (hhtts[q[tt]]s[i]) tt--;q[tt]i;}coutans;
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
} 二、 旅行问题
John 打算驾驶一辆汽车周游一个环形公路。 公路上总共有 n 个车站每站都有若干升汽油有的站可能油量为零每升油可以让汽车行驶一千米。 John 必须从某个车站出发一直按顺时针或逆时针方向走遍所有的车站并回到起点。 在一开始的时候汽车内油量为零John 每到一个车站就把该站所有的油都带上起点站亦是如此行驶过程中不能出现没有油的情况。 任务判断以每个车站为起点能否按条件成功周游一周。
输入 第一行是一个整数 n (3 ≤ n ≤ 1e6)表示环形公路上的车站数 接下来 n 行每行两个整数 pi,di (0 ≤ pi ≤ 2e9,0 ≤ di ≤ 2e9)分别表示表示第 i 号车站的存油量和第 i 号车站到 顺时针方向 下一站的距离。
输出 输出共 n 行如果从第 i 号车站出发一直按顺时针或逆时针方向行驶能够成功周游一圈则在第 i 行输出 TAK否则输出 NIE。
Input 5 3 1 1 2 5 2 0 1 5 4
Output TAK NIE TAK NIE TAK 解析 破链成环,可以根据顺时针和逆时针分开求; 下面先考虑顺时针的情况 开一个数组存储的是 当前点的油量*100-到下一点的距离的前缀和 ; 而我们判断的是 当前点绕一圈能否到达每一个点就等价于 从当前点开始到最后每一个点的前缀和是否都大于 0 ; 而判断每个点的前缀和是否都大于0就等价于判断最小值是否大于 0 ; 综上所述就转化为求以每个点为起点求在长度不超过 n 的数组的最小值是否大于0即 区间[i,in-1]的最小值是否大于0又转化成经典的滑动窗口问题 (为什么要判断每个点的前缀和大于0 如果能从起点到达当前点那一定是之前每个站点的油量*1000之和-到达之前点的每段距离大于0恰好就是这个新开数组能表达这种关系)
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N2e610;
int n;
int o[N],d[N];
int s[N];
int q[N];
bool vis[N];
void solve()
{cinn;for (int i1;in;i) cino[i]d[i];for (int i1;in;i) s[in]s[i]o[i]-d[i];for (int i1;i2*n;i) s[i] s[i-1];int hh0,tt0;q[0]2*n1;for (int i2*n;i0;i--){if (hhttq[hh]in) hh;if (in){if(s[q[hh]]-s[i]0) vis[i1]1;}while (hhtts[q[tt]]s[i]) tt--;q[tt]i;}d[0]d[n];for (int i1;in;i) s[in]s[i]o[i]-d[i-1];for (int i1;i2*n;i) s[i] s[i-1];hh0,tt0;q[0]0;for (int i1;i2*n;i){if (hhttq[hh]i-n) hh;if (in){if (s[i]-s[q[hh]]0) vis[i-n]1;}while (hhtts[q[tt]]s[i]) tt--;q[tt]i;}for (int i1;in;i){if (vis[i]) coutTAK\n;else coutNIE\n;}
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}
