【问题描述】 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
      
        2 using namespace std; 3 template
       
         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 }