Codeforces_352B_Jeff and Periods(排序)

时间:2022-10-24 15:31:33

题型:简单题


题意

有n个数,a1, a2, ..., an,现在想要找到所有的x,x满足:

1、x出现在这n个数中;

2、每一次出现的x的下标要满足等差数列。

按升序求出所有的x和x下标满足的公差d,如果x只出现一次,则d输出0。

样例解释:

          8

           1 2 1 3 1 2 1 5

下标:0 1 2 3 4 5 6 7

总共有4个满足条件的数,

1出现的下标为0 2 4 6,公差为2

2出现的下标为1 5,公差为4

3出现了一次,d为0

5出现了一次,d为0

所以输出;          4

                            1 2

                            2 4

                            3 0

                            5 0


分析

为了控制在O(n)时间内,用结构体保存这n个数及其下标,进行排序,然后再将数组扫一遍即可完成。


代码

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

struct node{
    int h,id;
}x[123456];

bool cmp(node a,node b){
    if(a.h == b.h) return a.id < b.id;
    else return a.h < b.h;
}

int v[123456],w[123456];

int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(v,0,sizeof(v));
        memset(w,0,sizeof(w));
        for(int i=0;i<n;i++){
            scanf("%d",&x[i].h);
            x[i].id=i;
        }
        x[n].h=9999999;
        x[n].id=n;
        n++;
        sort(x,x+n,cmp);
        /*
        for(int i=0;i<n;i++){
            printf("%d %d\n",x[i].h,x[i].id);
        }
        cout<<endl;
        */
        int cnt=1,iid=0,d=x[1].id-x[0].id;
        bool flag=true;
        for(int i=1;i<n;i++){
            if(x[i].h!=x[i-1].h){
                if(flag){
                    v[iid]=x[i-1].h;
                    if(cnt==1) w[iid]=0;
                    else w[iid]=d;
                    iid++;
                }
                cnt=1;
                flag=true;
                d=x[i+1].id-x[i].id;
            }
            else{
                if(flag){
                    if(d != x[i].id-x[i-1].id){
                        flag=false;
                        continue;
                    }
                    else cnt++;
                }
            }
        }
        printf("%d\n",iid);
        for(int i=0;i<iid;i++){
            printf("%d %d\n",v[i],w[i]);
        }
    }
    return 0;
}