【问题描述】 WZland的狂欢晚上上要举行许多的节目，其中一个项目就是多人组舞。来自WZland的 N个城市的居民各自选出了一名代表来参加多人组舞，每个人被标号为1..N。既然是多人组 舞，我们需要从这N个人中选取若干人一些人来（这就意味着不是每个人都能参加）。 负责选拔的人，仔细审核了这N个人的各项指标（包括腰围，胸围，身高……）给每个 人都打出了一个美观度，第i个人的美观度为Ai。接下来根据每个人的美观度，由国王来选 出参加组舞的人员。 国王是一个十分爱美的人，他对每件事情都有一个最低美观度标准S，如果一件事情的 美观度低于国王的评分标准，那么国王会放弃这件事情。 国王听说要让自己来选择参加组舞的人员，他十分头疼。但这是一件具有历史意义的大 事，他不好推辞，于是他让这N个人按编号从小到大排成一排。国王就在队伍中间走来走去， 不一会儿他就被这些人的美观度搞的头昏脑胀。为了使他挑选组舞的人选更加方便，国王决 定从队伍中选出编号连续的人来参加这次多人组舞，而这次组舞的美观度就是所有参加人员 的美观度之和。 虽说国王这样决定之后，对于挑选组舞人员更加方便了，但是由于国王的数学不好（这 个已经说明了好多次），他决定找你来帮忙。他想知道挑选那些人可以满足国王的美观度标 准。 当然会有很多种组合满足国王的要求，但国王想知道人数最少的那一组的人数。
【输入格式】 输入数据第一行包含两个整数N和S，分别表示参加选拔的人数和国王的最低美观度标 准。 接下一行有N个正整数。第i个正整数表示第i个人的美观度Ai。 【输出格式】 输出数据只包含一行一个整数 L，表示满足国王要求的人数最少的那一组的人数。
【样例】
输入：
6 10
1 2 1 2 5 3
输出：
3
【样例解释】 国王可以选取编号为 4、5、6 的人，并且这样人数最少。
【数据规模】 对于 30%的数据，N≤200； 对于 50%的数据，N≤2000； 对于 80%的数据，N≤200000. 对于 100%的数据，N≤2000000； 对于 100%的数据，Ai≤109，S≤ΣAi。
二分答案+枚举起点的优化
双指针也能过
1 #include<cstdio> 2 using namespace std; 3 template<class T> inline void read(T &_a){ 4 bool f=0;int _ch=getchar();_a=0; 5 while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();} 6 while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} 7 if(f)_a=-_a; 8 } 9 10 const int maxn=2000001; 11 long long n,a[maxn],s,sum[maxn]; 12 13 inline int check(int u,int fr) 14 { 15 for (register int i=fr;i<=n;++i) 16 if(sum[i]-sum[i-u]>=s) return i; 17 return 0; 18 } 19 20 int main() 21 { 22 freopen("dance.in","r",stdin); 23 freopen("dance.out","w",stdout); 24 read(n); read(s); 25 for (register int i=1;i<=n;++i) read(a[i]),sum[i]=sum[i-1]+a[i]; 26 int l=1,r=n,tmp2=1; 27 while(l<=r) 28 { 29 register int mid=l+r>>1,tmp; 30 if(tmp=check(mid,tmp2)) r=mid-1,tmp2=tmp; 31 else l=mid+1; 32 } 33 printf("%d",r+1); 34 return 0; 35 }