BOJ)14943 벼룩 시장

문제: icpc.me/14943

벼룩을 사려는 사람과 팔려는 사람이 있을 때 벼룩 거래에 발생하는 비용의 최솟값을 출력하는 문제이다.

문제를 잘 읽어보면 사려는 양과 팔려는 양은 같고, 거래에 발생하는 비용이 거래하는 두 사람의 거리에 비례한다.

우선 사려는 양과 팔려는 양이 같다는 점을 이용해, 항상 거래가 완전하게 이루어진다는 점을 생각해보면, 그냥 최대한 가깝게 거래를 매칭 시켜주는 그리디한 방법이 답이 된다는 걸 알 수 있다.

문제는 n이 10만으로 조금 크기 때문에 매칭을 일일이 직접 해줄 수는 없고, 투 포인터를 이용하여 처리해주면 깔끔하게 구현 가능하다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n,a[111111],res;
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    int idx=0;
    for(int i=1;i<n;){
        while(!a[idx])idx++;
        if(i==idx){
            i++;
            continue;
        }
        if(a[idx]*a[i]>=0){
            i++;
            continue;
        }
        if(abs(a[idx])>=abs(a[i])){
            res+=abs(a[i]*(idx-i));
            a[idx]+=a[i];
            a[i]=0;
            i++;
        }
        else{
            res+=abs(a[idx]*(idx-i));
            a[i]+=a[idx];
            a[idx]=0;
        }
    }
    printf("%lld\n",res);
    return 0;
}