想法-Codeforces-1144D Equalize Them All

題目連結

這道題對我來說最大的困難就是了解題意。。最近簡直要看英文題意看哭了…我一定好好學英語

大緻題意：輸出把所有數變成一樣大小所用的最小操作次數，以及每次操作i j對應的值

思路：可以看出操作1可以在a[i]<a[j]時，把a[i]變成a[j]，操作2可以在a[i]>a[j]時，把a[i]變成a[j]，是以隻需找出出現次數最多的數，把其他數都變成這個數即可。而且每次變化隻需進行一次操作。

AC代碼：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
long long a[200005];
long long flag[200005];
int main()
{
    long long n,i;
    scanf("%lld",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        flag[a[i]]++;
    }
    long long maxx=-1,k;
    for(i=0;i<=200000;i++)
    {
        if(flag[i]>maxx)
        {
            maxx=flag[i];
            k=i;//記錄出現次數最多的數字
        }
    }
    for(i=1;i<=n;i++)
    {
        if(a[i]==k)
        {
            k=i;//記錄出現次數最多的數字的一個位置
            break;
        }
    }
    printf("%lld\n",n-maxx);
    for(i=k-1;i>=1;i--)
    {
        if(a[i]<a[k])
            printf("1 %lld %lld\n",i,i+1);
        if(a[i]>a[k])
            printf("2 %lld %lld\n",i,i+1);
    }
    for(i=k+1;i<=n;i++)
    {
        if(a[i]<a[k])
            printf("1 %lld %lld\n",i,i-1);
        if(a[i]>a[k])
            printf("2 %lld %lld\n",i,i-1);
    }
}