鸽巢原理(入门优化) 之 poj 3370

在设计代码时，如还用上面方法， 1172ms

 1 //  [3/27/2014 Sjm]
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <queue>
 7 using namespace std;
 8 
 9 const int MAX_N = 100000;
10 int C, N;
11 struct node{
12     int x, y; 
13     friend bool operator < (const node &n1, const node &n2) {
14         if (n1.y == n2.y) return n1.x > n2.x;
15         else return n1.y > n2.y;
16     }
17 };
18 
19 void Solve(priority_queue<node> pri_que){
20     node n1 = pri_que.top();
21     pri_que.pop();
22     while (pri_que.size())
23     {
24         node n2 = pri_que.top();
25         pri_que.pop();
26         if (n1.y == n2.y) {
27             int myl = n1.x + 1, myr = n2.x;
28             if (myl == myr) {
29                 printf("%d
", myl);
30                 return;
31             }
32             else {
33                 for (int i = myl; i <= myr; i++){
34                     printf("%d", i);
35                     if (i != myr) printf(" ");
36                     else printf("
");
37                 }            
38                 return;
39             }
40         }
41         n1 = n2;
42     }
43     printf("no sweets
");
44 }
45 
46 int main(){
47     //freopen("input.txt", "r", stdin);
48     //freopen("output.txt", "w", stdout);
49     while (scanf("%d%d", &C, &N) && (C || N))
50     {
51         priority_queue<node> pri_que;
52         node n1;
53         n1.x = 0, n1.y = 0;
54         pri_que.push(n1);
55         int t, sum = 0;
56         for (int i = 0; i < N; i++){
57             scanf("%d", &t);
58             sum = (sum + t) % C;
59             n1.x = i + 1, n1.y = sum;
60             pri_que.push(n1);
61         }
62         Solve(pri_que);
63     }
64     return 0;
65 }

优化方法，增加标记 flag[MAX_N] ，829ms:

 1 //  [3/27/2014 Sjm]
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int MAX_N = 100000;
 9 int C, N, arr[MAX_N + 1];
10 
11 void Solve(){
12     int l = 0, r = 0, sum = 0;
13     vector<int> flag(C, 0);
14     for (int i = 1; i <= N; i++) {
15         sum = (sum + arr[i]) % C;
16         if (0 == sum) {
17             l = 1;
18             r = i;
19             break;
20         }
21         else {
22             if (flag[sum]) {
23                 l = flag[sum] + 1;
24                 r = i;
25                 break;
26             }
27             else flag[sum] = i;
28         }
29     }
30     for (int i = l; i <= r; i++) {
31         printf("%d", i);
32         if (i != r) printf(" ");
33         else printf("
");
34     }
35 }
36 
37 int main(){
38     //freopen("input.txt", "r", stdin);
39     //freopen("output.txt", "w", stdout);
40     while (scanf("%d%d", &C, &N) && (C || N))
41     {
42         for (int i = 1; i <= N; i++)
43             scanf("%d", &arr[i]);
44         Solve();
45     }
46     return 0;
47 }