蓝桥杯算法训练礼物

资源限制
时间限制：1.0s 内存限制：256.0MB问题描述
JiaoShou在爱琳大陆的旅行完毕，即将回家，为了纪念这次旅行，他决定带回一些礼物给好朋友。
在走出了怪物森林以后，JiaoShou看到了排成一排的N个石子。
这些石子很漂亮，JiaoShou决定以此为礼物。
但是这N个石子被施加了一种特殊的魔法。
如果要取走石子，必须按照以下的规则去取。
每次必须取连续的2*K个石子，并且满足前K个石子的重量和小于等于S，后K个石子的重量和小于等于S。
由于时间紧迫，Jiaoshou只能取一次。
现在JiaoShou找到了聪明的你，问他最多可以带走多少个石子。输入格式
第一行两个整数N、S。
第二行N个整数，用空格隔开，表示每个石子的重量。输出格式
第一行输出一个数表示JiaoShou最多能取走多少个石子。样例输入
8 3
1 1 1 1 1 1 1 1样例输出
6样列解释
任意选择连续的6个1即可。数据规模和约定
对于20%的数据：N<=1000
对于70%的数据：N<=100,000
对于100%的数据：N<=1000,000，S<=10^12，每个石子的重量小于等于10^9，且非负 方案1 前缀和

时间复杂度N*N(只能过20%的数据)

#includeusing namespace std;int N;//N个石子long long int S; //前k个石子的最大长度 int stone[1000000];//石子数组 long long int sum[1000000];//前缀和数组：第1个石子到第i+1个石子的总重量 int MAX;//能取走的最多石子个数 int main(){cin>>N>>S;for(int i=0; i>stone[i];//计算前缀和 if(i>0){sum[i] = sum[i-1] + stone[i]; }else{sum[i] = stone[i];}} //逐个尝试找到满足条件的K for(int i=1; i<=N/2; i++){//i即是题中的K for(int j=0; j<=N-2*i; j++){//j是开始的索引 //判断是否符合条件 ， 符合条件就更新MAX if(j==0){if(sum[j+i-1]<=S && sum[j+2*i-1]-sum[j+i-1]<=S){MAX = i*2;break;}}else{if(sum[j+i-1]-sum[j-1]<=S && sum[j+2*i-1]-sum[j+i-1]<=S){MAX = i*2;break;}}}}cout<

时间复杂度N*logN

#includeusing namespace std;int N;//N个石子long long int S; //前k个石子的最大长度 int stone[1000000];//石子数组 long long int sum[1000000];//前缀和数组：第1个石子到第i+1个石子的总重量 int MAX;//能取走的最多石子个数 bool flag;//是否找到满足条件的K int main(){//ios::sync_with_stdio(false);//输入优化,节省时间,或用scanf读数据 cin>>N>>S;for(int i=0; i>stone[i];//计算前缀和 if(i>0){sum[i] = sum[i-1] + stone[i]; }else{sum[i] = stone[i];}} //二分查找满足条件的K int L=1, R=N>>1; //左右边界[1...N/2] for(int i=L+((R-L)>>1); L<=R; i=L+((R-L)>>1)){//i即是题中的K , 且i=(L+R)/2 flag = false; for(int j=0; j<=N-2*i; j++){//j是开始的索引 //判断是否符合条件 ， 符合条件就更新MAX if(j==0){if(sum[j+i-1]<=S && sum[j+2*i-1]-sum[j+i-1]<=S){MAX = i*2;flag = true;break;}}else{if(sum[j+i-1]-sum[j-1]<=S && sum[j+2*i-1]-sum[j+i-1]<=S){MAX = i*2;flag = true;break;}}}//根据是否满足条件更新左右边界 if(flag){L = i+1;}else{R = i-1;}}cout<

时间复杂度 N*logN

#include#includeusing namespace std;int N;//N个石子long long int S; //前k个石子的最大长度 int stone[1000000];//石子数组 int L[1000000];//L[i] : 表示从第i+1个位置向左取石子(包括自己)，能取的最大石子个数 int R[1000000]; //R[i] : 表示从第i+1个位置向右取石子(包括自己)，能取的最大石子个数 int MAX;//能取走的最多石子个数 int main(){//ios::sync_with_stdio(false); //读入优化 cin>>N>>S;for(int i=0; i>stone[i];} //计算L[]数组 int i=0, j=0; //左右指针 i是区间左位置索引，j是区间右位置索引 long long int sum = 0;//区间石子重量之和 [i,j) 左闭右开 while(j=0){//判断左区间位置的石子是否可取if(sum+stone[i]<=S){//可取则增加左区间位置的石子 sum += stone[i];R[i] = j-i+1;i--;}else{//不可取则删去一个右区间位置的石子sum -= stone[j];j--;}}//遍历每一个位置，寻找最大的k for(int i=0; i