礼物

本题提供了两种方法，其中第一种为贪心，只过了90%的测试点，第二种是二分查找法，AC了

本题给了我一个很重要的提示，就是说一定要注意数据范围，注意long long 使用

贪心

贪心的思路很简单，就是一直拿，等到超了就不拿那个，然后把区间不断向后平移。
不过只过了90%，我很疑惑

/*
JiaoShou在爱琳大陆的旅行完毕，即将回家，为了纪念这次旅行，他决定带回一些礼物给好朋友。
在走出了怪物森林以后，JiaoShou看到了排成一排的N个石子。
石子很漂亮，JiaoShou决定以此为礼物。
但是这N个石子被施加了一种特殊的魔法。
如果要取走石子，必须按照以下的规则去取。每次必须取连续的2*K个石子，并且满足前K个石子的重量和小于等于S，
后K个石子的重量和小于等于S。由于时间紧迫，Jiaoshou只能取一次。
JiaoShou找到了聪明的你，问他最多可以带走多少个石子。第一行两个整数N、S。第二行N个整数，用空格隔开，表示每个石子的重量。
输出格式第一行输出一个数表示JiaoShou最多能取走多少个石子。
样列输入8 31 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，且非负
*/#include<iostream>using namespace std;const int N=10000100;long long a[N];
long long n,s;
long long ans=0;
long long sa[N]; 
long long k=0;int judge(long long f,long long k){long long tot=sa[f+k-1]-sa[f-1];if(tot<=s)return 1;return 0;
}int main(){cin>>n>>s;for(int i=1;i<=n;i++){cin>>a[i];sa[i]=a[i]+sa[i-1];}long long front,rear;front=rear=1;long long sum=0;while(rear<=n){while(sum<=s&&rear-1+k<=n){k=rear-front+1;sum+=a[rear];rear++;}//此循环退出了说明前半段和超过了，那么先把最后那个去掉 rear-=2;k=rear-front+1;//当前长度kif((rear+k)>n)break;if(judge(rear+1,k)){if(k>=ans)ans=k;}//如果后半段也满足要求，那么就看是否可以存入答案 sum-=a[rear+1];sum-=a[front];//为下一次循环做准备front++; rear++;}cout<<ans*2;//最后输出ans*2 return 0;
}

二分查找

二分查找的模板一定要注意，细节需要背下来，这个在之前的博客中有提到过，可以去看看。

刚开始一直不对，是二分细节没写好
后来也不对，是因为没有在check中加上判断if(i+2*a-1<=n)

/*
二分法太nb了 二分法适用于答案是一个整数，然后解在固定区间里面的 
*/#include<iostream>using namespace std;const int N=10000000;long long a[N];
long long sum[N];long long n,s;int check(int a){//给了一个a看看是否可以满足 //如果可以满足的话，那么找一下还有没有更大的，搜寻右半区间 //如果不能满足的话，说明不可能再找到一个更大的，搜寻左半区间 for(long long i=1;i+a-1<=n;i++){//i+a-1是以i为开始，长度为a的序列的末尾//即[i,i+a-1]//和[i+a,i+2a-1] if(i+2*a-1<=n){if(sum[i+a-1]-sum[i-1]<=s&&sum[i+2*a-1]-sum[i+a-1]<=s)return 1;}}return 0;
} int main(){cin>>n>>s;for(long long i=1;i<=n;i++){cin>>a[i];sum[i]=a[i]+sum[i-1];}long long  l=1,r=n;long long mid=(l+r+1)/2;long long ans=0;while(l<r){mid=(l+r+1)/2;if(check(mid)){//如果可能，再找找有没有更大的 l=mid;if(mid>=ans)ans=mid;}else{r=mid-1;}}cout<<ans*2<<endl;return 0;
}