[Codeforces][Round #732][Div.2] A : AquaMoon and Two Arrays (C++)

https://codeforces.com/contest/1546/problem/A

Problem - A - Codeforces

 

 

[난이도] Div.2
[유형] Greedy

[풀이]
최대 100번의 연산 내에 A배열을 B배열로 만들어야 합니다.
각 루프에서 i:0~N-1 루프를 돌면서 A[i]-B[i]가 가장 작은 값과 큰 값을 찾아서 저장한 뒤
A[i]-B[i]가 작은 A[i]는 +1, 큰 A[i]는 -1 을 해주면
이것이 매 루프마다 정답에 가장 유리한 연산이 됩니다.

100번내에 A=B를 만들 수 있으면 정답을 출력합니다.

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N,a[100],b[100],INF=987654321;

bool same(){
    for(int i=0;i<N;i++){
        if(a[i]!=b[i]) return false;
    }
    return true;
}
void prt(){
    for(int i=0;i<N;i++){
        printf("%d ",a[i]);
    }
    puts("");
}
void solve(){

    int it=100;
    vector<pair<int,int>> ans;
    while(it--){

        int minDiff=INF,minIdx=-1;
        int maxDiff=-INF,maxIdx=-1;
        bool ok=1;
        for(int i=0;i<N;i++){
            int d = a[i]-b[i];
            if(d!=0) ok=0;
            if(minDiff>d){
                minDiff=d;
                minIdx=i;
            }
            if(maxDiff<d){
                maxDiff=d;
                maxIdx=i;
            }
        }
        if(ok) break;

        a[minIdx]++;
        a[maxIdx]--;
        ans.push_back({maxIdx,minIdx});
    }
    if(same()){
        printf("%d\n",ans.size());
        for(auto p : ans){
            printf("%d %d\n",p.first+1,p.second+1);
        }
    }else{
        puts("-1");
    }
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        for(int i=0;i<N;i++) scanf("%d",&b[i]);
        solve();
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round732-Div.2/A.cpp