Valentine's Day Round 1001.Ferries Wheel（hdu 5174）解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5174

题目意思：给出 n 个人坐的缆车值，假设有 k 个缆车，缆车值 A[i] 需要满足：
A[i−1]<A[i]<A[i+1](1<i<K)。现在要求的是，有多少人满足，(他坐的缆车的值 + 他左边缆车的值) % INT_MAX == 他右边缆车的值。

　　首先好感谢出题者的样例三，否则真的会坑下不少人。即同一部缆车可以坐多个人。由于缆车的值是唯一的，所以可以通过排序先排出缆车的位置。求出满足条件的缆车的值，然后统计有多少人坐了即可。

　　一开始做的时候很不细心，出现runtime error，因为开了个vis[]数组来统计每部缆车坐的人数了，数据量是2147483647，很明显是错的。

　　然后就是考虑题目中的输出 -1（只有一部缆车）情况遗漏了，n == 1只是其中一种情况！因为缆车的值是独一无二的，那么排序后如果val[1] == val[n] 就能覆盖缆车只有一部的所有情况了。

　　最后就是没有用 long long (或 __int 64) 保存数据了。因为缆车的值最大是 2147483647，如果它左边的值（要相加嘛）是 1 以上，就会爆 int 了。

　　细心细心细心。。。细心。。。。。。

　　（1）简单版（学人写的）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 5;
 8 const __int64 I_MAX = 2147483647;
 9 __int64 a[maxn];
10 
11 int main()
12 {
13     #ifndef ONLINE_JUDGE
14         freopen("in.txt", "r", stdin);
15     #endif // ONLINE_JUDGE
16 
17     int n, cas = 0;
18     while (scanf("%d", &n) != EOF) {
19         for (int i = 1; i <= n; i++)
20             scanf("%I64d", &a[i]);
21         sort(a+1, a+1+n);
22         if (a[1] == a[n]) {     // 只有一部缆车的情况
23             printf("Case #%d: -1
", ++cas);
24             continue;      // 不要也行
25         }
26         else {
27             int ans = 0;
28             a[0] = a[n], a[n+1] = a[1];
29 
30             for (int i = 1; i <= n; i++) {
31                 int l = i, r = i;
32                 while (a[i] == a[l] && l >= 0)  // 定位左边的缆车值
33                     l--;
34                 while (a[i] == a[r] && r <= n+1)  // 定位右边的缆车值
35                     r++;
36                 if ((a[i]+a[l]) % I_MAX == a[r])
37                     ans++;
38             }
39             printf("Case #%d: %d
", ++cas, ans);
40         }
41     }
42     return 0;
43 }

（2）错了10次以上终于改正确的= =

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 100 + 5;
 9 const __int64 NUM = 2147483647;
10 
11 int main()
12 {
13     #ifndef ONLINE_JUDGE
14         freopen("in.txt", "r", stdin);
15     #endif // ONLINE_JUDGE
16     int n, cas = 0;
17     while (scanf("%d", &n) != EOF) {
18         __int64 val[maxn];
19         __int64 tmp[maxn];
20         for (int i = 0; i < n; i++) {
21             scanf("%I64d", &tmp[i]);
22         }
23         sort(tmp, tmp+n);
24         if (tmp[0] == tmp[n-1])
25             printf("Case #%d: -1
", ++cas);
26         else {
27             int c = 0;
28             for (int i = 0; i < n; i++) {
29                 while (tmp[i] == tmp[i+1] && i < n)
30                     i++;
31                 val[c++] = tmp[i];
32             }
33 
34             int ans = 0;
35             if ((val[0] + val[c-1]) % NUM == val[1]) {
36                 for (int j = 0; j < n; j++) {
37                     if (tmp[j] == val[0])
38                         ans++;
39                 }
40             }
41             if ((val[c-1] + val[c-2]) % NUM == val[0] && val[c-1] != val[0]) {
42                 for (int j = n-1; j >= 0; j--) {
43                     if (tmp[j] == val[c-1])
44                         ans++;
45                 }
46             }
47             for (int i = 1; i < c-1; i++) {
48                 if ((val[i] + val[i-1]) % NUM == val[i+1] && val[i] != val[0] && val[i] != val[c-1]) {
49                     for (int j = i; j < n; j++) {
50                         if (tmp[j] == val[i])
51                             ans++;
52                     }
53                 }
54             }
55             printf("Case #%d: %d
", ++cas, ans);
56         }
57     }
58     return 0;
59 }

View Code