题解：枚举公差，a[2]的操作有三种情况：a[2]+1,a[2],a[2]-1；a[1]的操作有三种情况：a[1]+1,a[1],a[1]-1。
1 #pragma warning(disable:4996) 2 #include<string> 3 #include<queue> 4 #include<cstdio> 5 #include<cstring> 6 #include<iostream> 7 #include<algorithm> 8 #define ll long long 9 using namespace std; 10 11 const int maxn = 100005; 12 const int INF = 1e9 + 7; 13 14 int n; 15 int a[maxn]; 16 17 int cal(int d,int last) { 18 int cnt = 0; 19 for (int i = 3; i <= n; i++) { 20 if (a[i] - last == d) { 21 last = a[i]; 22 } 23 else if (a[i] - 1 - last == d) { 24 cnt++; 25 last = a[i] - 1; 26 } 27 else if (a[i] + 1 - last == d) { 28 cnt++; 29 last = a[i] + 1; 30 } 31 else return -1; 32 } 33 return cnt; 34 } 35 36 int main() 37 { 38 while (cin >> n) { 39 for (int i = 1; i <= n; i++) cin >> a[i]; 40 if (n == 1 || n == 2) cout << "0" << endl; 41 else { 42 int ans = INF; 43 44 int d1 = a[2] + 1 - a[1]; 45 int last = a[2] + 1; 46 int x = cal(d1, last); 47 if (x != -1) ans = min(ans, x + 1); 48 49 d1 = a[2] + 2 - a[1]; 50 last = a[2] + 1; 51 x = cal(d1, last); 52 if (x != -1) ans = min(ans, x + 2); 53 54 d1 = a[2] - (a[1] + 1); 55 last = a[2]; 56 x = cal(d1, last); 57 if (x != -1) ans = min(ans, x + 1); 58 59 d1 = a[2] - (a[1] - 1); 60 last = a[2]; 61 x = cal(d1, last); 62 if (x != -1) ans = min(ans, x + 1); 63 64 d1 = a[2] - 1 - (a[1] + 1); 65 last = a[2] - 1; 66 x = cal(d1, last); 67 if (x != -1) ans = min(ans, x + 2); 68 69 d1 = a[2] - 1 - a[1]; 70 last = a[2] - 1; 71 x = cal(d1, last); 72 if (x != -1) ans = min(ans, x + 1); 73 74 d1 = a[2] - a[1]; 75 last = a[2]; 76 x = cal(d1, last); 77 if (x != -1) ans = min(ans, x); 78 79 d1 = (a[2] + 1) - (a[1] + 1); 80 last = a[2] + 1; 81 x = cal(d1, last); 82 if (x != -1) ans = min(ans, x + 2); 83 84 d1 = (a[2] - 1) - (a[1] - 1); 85 last = a[2] - 1; 86 x = cal(d1, last); 87 if (x != -1) ans = min(ans, x + 2); 88 89 if (ans == INF) { 90 cout << "-1" << endl; 91 } 92 else cout << ans << endl; 93 } 94 } 95 return 0; 96 }
题解：前缀和表示当前这个车站相对于起点（起点车站标为：0）下了多上人或者上了多少人。那么Max和Min分别表示极限情况。Min说明起点至少有多少人(abs(Min))，Max说明起点至多能有多少人（m-Max)。所以答案就是（m-Max)-abs(Min)+1。
1 #pragma warning(disable:4996) 2 #include<string> 3 #include<queue> 4 #include<cstdio> 5 #include<cstring> 6 #include<iostream> 7 #include<algorithm> 8 #define ll long long 9 using namespace std; 10 11 const int maxn = 1005; 12 13 int n, m; 14 15 int main() 16 { 17 while (cin >> n >> m) { 18 int res = 0, Max = 0, Min = 0; 19 for (int i = 1; i <= n; i++) { 20 int d; 21 cin >> d; 22 res += d; 23 Max = max(Max, res); 24 Min = min(Min, res); 25 } 26 int ans = m - Max + min(0, Min) + 1; 27 if (ans < 0) { 28 cout << 0 << endl; 29 } 30 else { 31 cout << ans << endl; 32 } 33 } 34 return 0; 35 }
题解：哈希后求前缀和，可以得到小于当前数的有多少个，然后统计争吵中小于当前数的有多少个。
感受：这题没多大意思，因为给出的争吵关系不具有传递性~~~，如果有传递性就灰常麻烦了，我还多写了并查集 ：( 。
#pragma warning(disable:4996) #include<map> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn = 200005; int n, m; int pa[maxn], d[maxn], c[maxn], cnt[maxn], ans[maxn]; map<int, int> p; int Find(int a) { if (a == pa[a]) return a; return pa[a] = Find(pa[a]); } void Union(int a, int b) { int x = Find(a); int y = Find(b); if (x != y) pa[y] = x; } void Inite() { p.clear(); memset(cnt, 0, sizeof(cnt)); memset(ans, 0, sizeof(ans)); for (int i = 1; i <= n; i++) pa[i] = i; } int main() { while (scanf("%d%d", &n, &m) != EOF) { Inite(); for (int i = 1; i <= n; i++) { scanf("%d", &c[i]); d[i] = c[i]; } sort(d + 1, d + n + 1); int k = unique(d + 1, d + n + 1) - (d + 1); for (int i = 1; i <= k; i++) p[d[i]] = i; for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); if (c[u] > c[v]) ans[u]++; if (c[u] < c[v]) ans[v]++; } cnt[0] = 0; for (int i = 1; i <= n; i++) cnt[p[c[i]]]++; for (int i = 1; i <= k; i++) cnt[i] += cnt[i - 1]; for (int i = 1; i <= n; i++) { cout << cnt[p[c[i]] - 1] - ans[i] << endl; } } return 0; }