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）简单版（学人写的）

　　

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int maxn = 100 + 5;
const __int64 I_MAX = 2147483647;
__int64 a[maxn];

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    int n, cas = 0;
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%I64d", &a[i]);
        sort(a+1, a+1+n);
        if (a[1] == a[n]) {     // 只有一部缆车的情况
            printf("Case #%d: -1\n", ++cas);
            continue;      // 不要也行
        }
        else {
            int ans = 0;
            a[0] = a[n], a[n+1] = a[1];

            for (int i = 1; i <= n; i++) {
                int l = i, r = i;
                while (a[i] == a[l] && l >= 0)  // 定位左边的缆车值
                    l--;
                while (a[i] == a[r] && r <= n+1)  // 定位右边的缆车值
                    r++;
                if ((a[i]+a[l]) % I_MAX == a[r])
                    ans++;
            }
            printf("Case #%d: %d\n", ++cas, ans);
        }
    }
    return 0;
}

 

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

　　

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100 + 5;
const __int64 NUM = 2147483647;

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    int n, cas = 0;
    while (scanf("%d", &n) != EOF) {
        __int64 val[maxn];
        __int64 tmp[maxn];
        for (int i = 0; i < n; i++) {
            scanf("%I64d", &tmp[i]);
        }
        sort(tmp, tmp+n);
        if (tmp[0] == tmp[n-1])
            printf("Case #%d: -1\n", ++cas);
        else {
            int c = 0;
            for (int i = 0; i < n; i++) {
                while (tmp[i] == tmp[i+1] && i < n)
                    i++;
                val[c++] = tmp[i];
            }

            int ans = 0;
            if ((val[0] + val[c-1]) % NUM == val[1]) {
                for (int j = 0; j < n; j++) {
                    if (tmp[j] == val[0])
                        ans++;
                }
            }
            if ((val[c-1] + val[c-2]) % NUM == val[0] && val[c-1] != val[0]) {
                for (int j = n-1; j >= 0; j--) {
                    if (tmp[j] == val[c-1])
                        ans++;
                }
            }
            for (int i = 1; i < c-1; i++) {
                if ((val[i] + val[i-1]) % NUM == val[i+1] && val[i] != val[0] && val[i] != val[c-1]) {
                    for (int j = i; j < n; j++) {
                        if (tmp[j] == val[i])
                            ans++;
                    }
                }
            }
            printf("Case #%d: %d\n", ++cas, ans);
        }
    }
    return 0;
}