codeforces 1144D（思维）

dejavu1zz

发布于 2020-10-23 15:24:34

3300

发布于 2020-10-23 15:24:34

题意描述

You are given an array a consisting of n integers. You can perform the following operations arbitrary number of times (possibly, zero):

Choose a pair of indices (i,j) such that |i−j|=1 (indices i and j are adjacent) and set ai:=ai+|ai−aj|; Choose a pair of indices (i,j) such that |i−j|=1 (indices i and j are adjacent) and set ai:=ai−|ai−aj|. The value |x| means the absolute value of x. For example, |4|=4, |−3|=3.

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 1018 by absolute value.

每次进行两种操作，求将数组中的一个数变成所有数的最小次数

思路

我们发现两个操作一定能使两个相邻的数相同，所以我们找出众数，然后从左到右，从右到左遍历一遍即可。如果比众数小则需要进行第二个操作，否则进行第一个操作。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2*1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int a[N];
void solve(){
    map<int,int> mp;
    int n;cin>>n;
    rep(i,1,n+1){
        cin>>a[i];
        mp[a[i]]++;
    }
    int MAX=-1,max_val;
    for(auto m : mp){
        if(m.y>MAX){
            MAX=m.y;
            max_val=m.x;
        }
    }
    if(MAX==n) cout<<0<<endl;
    else{
        cout<<n-MAX<<endl;
        int idx=0;
        rep(i,1,n+1){
            if(a[i]==max_val){
                idx=i;
                break;
            }
        }
        rrep(i,idx,1){
            if(a[i]<max_val) cout<<1<<' '<<i<<' '<<i+1<<endl;
            if(a[i]>max_val) cout<<2<<' '<<i<<' '<<i+1<<endl;
        }
        rep(i,idx,n+1){
            if(a[i]>max_val) cout<<2<<' '<<i<<' '<<i-1<<endl;
            if(a[i]<max_val) cout<<1<<' '<<i<<' '<<i-1<<endl;
        }
    }
}
int main(){
    IOS;
    solve();
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/28 ，如有侵权请联系 cloudcommunity@tencent.com 删除

absolute