[백준] 19464 - King's Roads (c++)

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

 

문제 요약

도시 n개를 모두 잇는 도로망을 새로 구축 할 것이다. 각 도시에 살고 있는 인구 수가 주어진다. 도시 사이에 도로를 하나 놓는데에 각 도시의 인구 합만큼 비용이 드는데 합이 m을 넘어가면 m만큼 할인된다. 도로망을 구축하는데 드는 최소 비용을 구해라.

 

풀이 (N)

• MST
• 투포인터

일단 정렬을 한다. 할인을 받을 수 없는 정점은 모두 첫번째 정점과 이어준다. 할인을 받을 수 있는 정점은 투포인터를 이용해 이어줄 수 있다. 할인 받을 수 있는 첫번째 정점을 l 마지막 정점을 r로 두고 l과 r-1을 이어도 할인을 받을 수 있다면 r-- 아니면 l++를 해주면서 l과r을 이어주는 것을 할인 받을 수 있는 모든 정점이 이어질 때까지 반복한다. 그럼 컴포넌트가 두개로 나뉘는데 첫번째 정점을 할인 받을 수 있는 첫번째 정점과 이어주며 MST로 만들 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n,m;cin>>n>>m;
    int a[n];
    for(int& x:a)cin>>x;
    sort(a,a+n);
    
    int l=0,r=n-1; ll ans=0;
    for(;l<n;) {
        if(a[l]+a[n-1]<m) {
            if(++l<n)   
                ans+=a[l]+a[0];
        }
        else break;
    }
    for(;l<r;) {
        ans+=a[l]+a[r]-m;
        if(a[l]+a[r-1]>=m)r--;
        else l++;
    }
    cout<<ans;
}