蓝桥杯 算法训练 礼物

资源限制
时间限制：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%的数据)

#include

using 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< 
方案2 前缀和 + 二分查找 
时间复杂度N*logN 
#include

using 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< 
方案3 双指针 
时间复杂度 N*logN 
#include
#include

using 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