百题计划-2 codeforces1185D Extra Element 暴力

https://codeforces.com/contest/1185/problem/D

题意：给一个序列，移除一个数然后排序后使得序列成为等差数列，求移除的下标。

解法：

先排序，把所有差值扔到map里，显然，移除一个数最多去掉两个差值，所以map.size-2不能大于1.

然后遍历数组，修改map检查，或遍历map的差值，检查数组均可，这里选择遍历map检查数组更好写。

但有一个坑点，如果数组排序后本身是等差数列，则移除首项，注意！！这里的首项是排序后的，应该输出排序前的id，不能直接输出1.

#include<bits/stdc++.h>

#define sz(v) (int)v.size()

using namespace std;

typedef long long ll;

const int maxn=1000100;

const int INF=(1<<29);

int n;

struct Node{

    ll x;

    int id;

    friend bool operator<(Node A,Node B){

        return A.x<B.x;

    }

};Node p[maxn];

map<ll,int> mp;

int check(ll d){

    // 1

    int cnt=0;

    ll t=p[1].x;

    vector<int> v;

    for(int i=1;i<=n;i++){

        if(p[i].x!=t) cnt++,v.push_back(p[i].id);

        else t+=d;

    }

    if(cnt==0) return p[1].id;

    if(cnt==1) return v[0];

    // n

    cnt=0;t=p[n].x;v.clear();

    for(int i=n;i>=1;i--){

        if(p[i].x!=t) cnt++,v.push_back(p[i].id);

        else t-=d;

    }

    if(cnt==0) return p[1].id;

    if(cnt==1) return v[0];

    return -1;

}

void solve(){

    mp.clear();

    for(int i=1;i<=n;i++) cin>>p[i].x,p[i].id=i;

    sort(p+1,p+n+1);

    for(int i=2;i<=n;i++) mp[p[i].x-p[i-1].x]++;

    if(n<=3){

        puts("1");return;

    }

    if(sz(mp)-2>1){

        puts("-1");return;

    }

    for(map<ll,int>::iterator it=mp.begin();it!=mp.end();++it){

        int index=check(it->first);

        if(index!=-1){

            cout<<index<<endl;return;

        }

    }

    puts("-1");

}

int main(){

    // freopen("in.txt","r",stdin);

    while(cin>>n) solve();

    return 0;

}

巴特西

百题计划-2 codeforces1185D Extra Element 暴力

最新文章

热门文章