[BOJ 23578] 비 오는 날

https://www.acmicpc.net/problem/23578

23578번: 비 오는 날

Tag : greedy

 

문제요약

스패닝 트리를 만드는데 $\sum (degre{e}_i{)}^2\ast a_i$를 최소화해라

 

풀이

처음에 이상한 전략을 많이 생각했다.

일단 $a_i$에 비례하게 분배해놓고 이득이 되는 쪽으로 옮긴다던지....

그런데 이걸 잘 정리하다보니까 그냥 처음부터 최소화되는 쪽으로 이어가는게 낫다는 결론이 나왔다.

 

일단 모든 정점에서 $degre{e}_i$가 1 이상이라면 스패닝 트리는 무조건 만들 수 있다.

그럼 나머지 N - 2개의 degree를 어떻게 분배하냐는 간단하다. 

$degre{e}_i$을 1 증가시켰을 때 증가율은 $2degre{e}_i+1$인데

그때그때 이것이 작은 순으로 넣어주면 된다.

 

그때그때의 증가율이 작은순으로 넣은 것보다 작은 해가 존재한다고 가정하자.

증가율이 작은 순대로 만든 최소 비용을 ans라고 하면 여기서 증가율이 작은 것을 다른 것으로 대체했을 때

이 비용이 ans보다 작아야한다. i번 정점의 degree를 하나 줄이고 그것이 아닌 증가율이 가장 작지 않은 j를 삽입한다 했을 때

이 때의 답은 $ans+(-2degre{e}_i+1)+(2degre{e}_j+1)$이 된다. 

이것이 ans보다 작으려면 $2degre{e}_i-1>2degre{e}_j+1$이어야하는데 이것을 만족하려면 위의 가정에 모순된다.

따라서 위 그리디가 성립한다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

ll n;
ll a[303030];
ll b[303030];
priority_queue<pair<ll, ll>> pq;

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
template<typename T>
struct FASTIO {
    char *p,O[2000000],*d;
    void set() {
        struct stat st;fstat(0, &st);d=O;
        p=(char*)mmap(0,st.st_size,1,1,0,0);
    }
    ~FASTIO() {
        write(1,O,d-O);
    }
    inline T get() {
        T x=0;bool e;p+=e=*p=='-';
        for(char c=*p++;c&16;x=10*x+(c&15),c=*p++);
        return e?-x:x;
    }
    inline void put(int x) {
        if(x<0) *d++='-', x=-x;
        char t[16], *q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=10;
    }
};

FASTIO<int> IO;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);

    IO.set();
    n = IO.get();
    if(n == 1) return cout << 0 << endl, 0;
    for(int i=1; i<=n; i++) {
        a[i] = IO.get(); b[i] = 1;
        pq.push({-3 * a[i], i});
    }
    for(int t=0; t<n-2; t++) {
        auto [x, idx] = pq.top(); pq.pop();
        b[idx]++;
        pq.push({-(2 * b[idx] + 1) * a[idx], idx});
    }
    ll ans = 0;
    for(int i=1; i<=n; i++) {
        ans += a[i] * b[i] * b[i];
    }
    cout << ans << endl;
}