2010-02-01.ural1061-pku1754
簡(jiǎn)單題，按照*分成不同的段，然后在每個(gè)段中線性掃描即可。
注意輸出的是有最小值的一段的開(kāi)始位置。
1
2 const int N = 100100;
3 void ckmin(int &a,int b) { if(a > b) a = b; }
4 int n,k;
5 int s[N],top,res,rl,curl,offset;
6
7 int calc()
8 {
9 if (top < k) { return maxint; }
10 int i,j,cur = maxint,tmp = 0;
11 for (i = 0;i < k-1;i++) {
12 tmp += s[i];
13 }
14 for (i = k-1;i < top;i++) {
15 tmp += s[i];
16 if (tmp < cur) {
17 cur = tmp;
18 curl = i-k+2 + offset;
19 }
20 tmp -= s[i-k+1];
21 }
22 return cur;
23 }
24
25 char buf[N];
26 int main()
27 {
28 int i,j;
29 char t;
30 scanf("%d%d\n",&n,&k);
31 res = maxint;
32 for (i = 0;i < n;i++) {
33 t = getchar();
34 while (t == '\n' || t == '\r') {
35 t = getchar();
36 }
37 buf[i] = t;
38 }
39 buf[i] = '*';
40
41 for (i = 0;i <= n;i++) {
42 t = buf[i];
43 if (t == '*') {
44 int tmp = calc();
45 if (tmp < res) {
46 res = tmp;
47 rl = curl;
48 }
49 offset = i+1;
50 top = 0;
51 }else {
52 s[top++] = t - '0';
53 }
54 }
55 if (res == maxint) {
56 printf("0\n");
57 }else {
58 printf("%d\n",rl);
59 }
60 return 0;
61 }
62