CodeForces 1144D

原题https://vjudge.net/problem/CodeForces-1144D

/*求序列就经过几次step变成同一个数，
其实能发现一个数经过step1或者step2变成相邻的数，
所以要经过最小次数变成同一个数字，
就是先求出出现次数最多的数字，然后把所有的其他数字都变成这个数字。
注意，出现次数最多的数字可能不相邻，序列是乱序的。
先记录数字的位置，然后从该位置往前遍历序列，
比这个数字大，就执行step2，比这个数字小，就执行step1，
结束后，再从该位置往后遍历，比这个数字大，就执行step2，比这个数字小，就执行step1.


输出中  第一行是进行了几次操作
第二行 第一个数字  进行的操作的代号 第二个和第三个是进行操作的两个数字*/
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+10;
int a[MAX],b[MAX];
int main() {
    int n;
    cin>>n;
    int maxx=0,num,pos=0;
    for(int i=1; i<=n; i++) {
        cin>>a[i];      //a[i]为输入的数字 
        b[a[i]]++;     //b[a[i]]  记录相应数字出现的次数 
        if(b[a[i]]>maxx) {
            maxx=b[a[i]];         //出现次数最多的   
            pos=i;        //标记位置 
        }
    }
    cout<<n-b[a[pos]]<<endl;
    if(pos>1) {
        for(int j=pos-1; j>=1; j--) {
            if(a[j]==a[pos])        continue;
            if(a[j]>a[j+1])cout<<2<<" "<<j<<" "<<j+1<<endl;
            else cout<<1<<" "<<j<<" "<<j+1<<endl;
            a[j]=a[pos];
        }
    }
    for(int k=pos+1; k<=n; k++) {
        if(a[k]==a[pos])continue;
        if(a[k]>a[k-1])cout<<2<<" "<<k<<" "<<k-1<<endl;
        else cout<<1<<" "<<k<<" "<<k-1<<endl;
        a[k]=a[pos];
    }
    return 0;
}