cf 568 div2
题意：
给你一个无序的序列，问能否去掉一个数，使得剩下的数组成一个等差数列，如果可以，输出去掉的数原来的下标，不能就输出-1
题解：
思路大概就是找出可能不合理的数，去掉看检查数列是否合理，下面列出了各种情况。。。太长了，建议看我大佬博客
#include#include using std::sort;struct node{ int i, num;}a[200010];bool cmp(node x, node y) { return x.num < y.num;}int main() { int n, num1, num2, num3, cnt1 = 0, cnt2 = 0, cnt3 = 0, ans1 = -1000000010, ans2 = -1000000010, ans3 = -1000000010, flag = 0; int b[200010]; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &a[i].num), a[i].i = i, b[i] = a[i].num; sort(a, a + n, cmp); for(int i = 1; i < n; i++) {//记录出现不同的差 if(ans1 == -1000000010) { ans1 = a[i].num - a[i-1].num; cnt1++; num1 = a[i].i + 1; } else if(a[i].num - a[i-1].num == ans1) { cnt1++; } else if(ans2 == -1000000010) { ans2 = a[i].num - a[i-1].num; cnt2++; num2 = a[i].i + 1; } else if(ans2 == a[i].num - a[i-1].num) { cnt2++; } else if(ans3 == -1000000010) { ans3 = a[i].num - a[i-1].num; cnt3++; num3 = a[i].i + 1; } else if(ans3 == a[i].num - a[i-1].num) { cnt3++; } else {//如果有四个差不同，不可能组成等差数列了 flag = 1; break; } } if(flag) printf("-1\n"); else { if(n < 4 || cnt1 == n - 1) printf("%d\n", a[0].i+1);//已经是等差数列或者n<4 else if(cnt1 == 1 && cnt2 == n - 2 && num1 == a[1].i + 1) printf("%d\n", a[0].i + 1);//去掉最小那个 else if(cnt2 == 1 && cnt1 == n - 2) {//出出现两种不同的差，且其中一种是只出现一次 if(num2 == a[n-1].i + 1) printf("%d\n", num2);//例如1 2 3 8 else {//1 2 2 3 4，思路，去掉2，检验剩下的数列是否合理 int flagg = 1; for(int i = 1; i < n; i++) { if(a[i].num == b[num2 - 1] && flagg) { i++; if(a[i].num - a[i-2].num != ans1) { flag = 1; break; } flagg = 0; continue; } if(a[i].num - a[i-1].num != ans1) { flag = 1; break; } } if(flag) printf("-1\n");//不合理 else printf("%d\n", num2);//合理 } } else if(n == 4) {//这个比较特殊 if(ans1 + ans2 == ans3) printf("%d\n", a[1].i + 1);//1 2 3 5 else if(ans1 == ans2 + ans3) printf("%d\n", a[2].i + 1);//1 3 4 5 else printf("-1\n"); } else {//去掉可能不合理的，检验剩下的数列是否合理 int flagg = 1; if(cnt1 == n - 3) {//为什么这里要判完ans1还要判ans2呢，例子：1 2 3 5 7 for(int i = 1; i < n; i++) { if(a[i].num == b[num2 - 1] && flagg) { i++; if(a[i].num - a[i-2].num != ans1) { flag = 1; break; } flagg = 0; continue; } if(a[i].num - a[i-1].num != ans1) { flag = 1; break; } } if(flag) { flag = 0, flagg = 1; if(cnt2 == n - 3) { for(int i = 1; i < n; i++) { if(a[i].num == b[num1 - 1] && flagg) { i++; if(a[i].num - a[i-2].num != ans2) { flag = 1; break; } flagg = 0; continue; } if(a[i].num - a[i-1].num != ans2) { flag = 1; break; } } if(flag) printf("-1\n"); else printf("%d\n", num1); } else printf("-1\n"); } else printf("%d\n", num2); } else if(cnt2 == n - 3) { for(int i = 1; i < n; i++) { if(a[i].num == b[num1 - 1] && flagg) { i++; if(a[i].num - a[i-2].num != ans2) { flag = 1; break; } flagg = 0; continue; } if(a[i].num - a[i-1].num != ans2) { flag = 1; break; } } if(flag) printf("-1\n"); else printf("%d\n", num1); } else if(cnt3 == n - 3) { for(int i = 1; i < n; i++) { if(a[i].num == b[num1 - 1] && flagg) { i++; if(a[i].num - a[i-2].num != ans3) { flag = 1; break; } flagg = 0; continue; } if(a[i].num - a[i-1].num != ans3) { flag = 1; break; } } if(flag) printf("-1\n"); else printf("%d\n", num1); } else printf("-1\n"); } } return 0;}