PAT 1044

题目链接：http://pat.zju.edu.cn/contests/pat-a-practise/1044

设置i,j两个游标，初始为0，cnum=a[i]+...+a[j]，

1.if(cnum<M) cnum+=a[++j];

2. 如果cnum>=M ，表示i,j切割方案可能为目前最佳，比较下即可，看是否需要置换当前的切割方案，然后 cnum -=a[i++]

 1 #include<cstdio>
 2 #include<vector>
 3 #include<utility>
 4 using namespace std;
 5 
 6 
 7 int main(){
 8     int N,M;
 9     scanf("%d%d", &N,&M);
10     vector<int> a(N+1);
11     vector<pair<int,int>> outcome;
12     for(int i=0; i<N; ++i){
13         scanf("%d", &a[i]);
14     }
15     int i(0),j(0),min(1<<30),cnum(a[0]);
16     while(i<N && j<N){
17         if(cnum >= M){
18             if(cnum < min){
19                 min = cnum;
20                 outcome.clear();
21                 outcome.push_back(make_pair(i+1, j+1));
22             }
23             else if(cnum == min){
24                 outcome.push_back(make_pair(i+1, j+1));
25             }
26             cnum -= a[i++];
27         }    
28         else
29             cnum+=a[++j];
30     }
31 
32     int length=outcome.size();
33     for(i=0; i<length; ++i)
34         printf("%d-%d
", outcome[i].first, outcome[i].second);
35     return 0;
36 }