hdu 4476 Cut the rope (2-pointer && simulation)

　　题意是，给出若干绳子，对同一根绳子只能切割一次，求出最多能获得多少长度相同的绳子。

　　代码中，s是最大切割长度，而当前切割长度为t/2.

代码如下：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 
 6 using namespace std;
 7 
 8 const int N = 111111;
 9 int cnt[N];
10 
11 int main() {
12     int T, n;
13     cin >> T;
14     while (T-- && cin >> n) {
15         memset(cnt, 0, sizeof(cnt));
16         for (int i = 0, x; i < n; i++) {
17             scanf("%d", &x);
18             cnt[x]++;
19         }
20         int s = 1, t = 1, mx = 0;
21         while (s < N) {
22             while (t < N && t <= (s << 1)) {
23                 mx = max(mx, cnt[t] + n);
24                 t++;
25             }
26             n -= cnt[s++];
27         }
28         cout << mx << endl;
29     }
30     return 0;
31 }

View Code

——written by Lyon