Codeforces1144D(D题）Equalize Them All

发布时间：2020-12-15 05:35:10 所属栏目：Java 来源：网络整理

导读：D. Equalize Them All You are given an array? a a?consisting of? n n?integers. You can perform the following operations arbitrary number of times (possibly,zero): Choose a pair of indices? ( i , j ) (i,j)?such that? | i ? j | = 1 |i?j|=1?(i

You are given an array?

Choose a pair of indices?
Choose a pair of indices?

The value?

Your task is to find the minimum number of operations required to obtain the array of equal elements and print the order of operations to do it.

It is guaranteed that you always can obtain the array of equal elements using such operations.

Note that after each operation each element of the current array should not exceed?

Input

The first line of the input contains one integer?

The second line of the input contains?

Output

In the first line print one integer?

In the next?

Note that after each operation each element of the current array should not exceed?

If there are many possible answers,you can print any.

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,a[200010],cnt[200010],mx=-1,mxd;
 5 int main() {
 6     cin>>n;
 7     for(int i=1; i<=n; i++) {
 8         cin>>a[i];
 9         cnt[a[i]]++;
10     }
11     for(int i=0; i<=200000; i++) 
12         if(cnt[i]>mx) {
13             mx=cnt[i];
14             mxd=i;
15         }
16     cout<<n-mx<<endl;
17     for(int i=2; i<=n; i++) { 
18         if(a[i-1]!=mxd)continue;
19         if(a[i]>a[i-1])cout<<2<<" "<<i<<" "<<i-1<<endl;
20         if(a[i]<a[i-1])cout<<1<<" "<<i<<" "<<i-1<<endl;
21         a[i]=a[i-1];
22     }
23     for(int i=n-1; i>=1; i--) { 
24         if(a[i+1]!=mxd)continue;
25         if(a[i]>a[i+1])cout<<2<<" "<<i<<" "<<i+1<<endl;
26         if(a[i]<a[i+1])cout<<1<<" "<<i<<" "<<i+1<<endl;
27         a[i]=a[i+1];
28     }
29     return 0;
30 }

思路分析：先找出最多次数的数字，然后向左向右循环比较，向左时，如果左元素小，通过2方式来变为出现最多次数字。如果左元素大，通过1方式来变为出现最多次数字。向右同理。

题目链接：https://codeforces.com/contest/1144/problem/D

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!