cf 568 div2 d
题意：
给你一个无序的序列，问能否去掉一个数，使得剩下的数组成一个等差数列，如果可以，输出去掉的数原来的下标，不能就输出-1
题解：
思路大概就是找出可能不合理的数，去掉看检查数列是否合理，下面列出了各种情况。。。太长了，建议看我大佬博客_kangkang
#include <cstdio>
#include <algorithm>
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
");
else {
if(n < 4 || cnt1 == n - 1) printf("%d
", a[0].i+1);//已经是等差数列或者n<4
else if(cnt1 == 1 && cnt2 == n - 2 && num1 == a[1].i + 1) printf("%d
", a[0].i + 1);//去掉最小那个
else if(cnt2 == 1 && cnt1 == n - 2) {//出出现两种不同的差，且其中一种是只出现一次
if(num2 == a[n-1].i + 1) printf("%d
", 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
");//不合理
else printf("%d
", num2);//合理
}
}
else if(n == 4) {//这个比较特殊
if(ans1 + ans2 == ans3) printf("%d
", a[1].i + 1);//1 2 3 5
else if(ans1 == ans2 + ans3) printf("%d
", a[2].i + 1);//1 3 4 5
else printf("-1
");
}
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
");
else printf("%d
", num1);
}
else printf("-1
");
}
else printf("%d
", 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
");
else printf("%d
", 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
");
else printf("%d
", num1);
}
else printf("-1
");
}
}
return 0;
}