[TIOJ 1130] Dark Kingdom II

作法：

greedy，但寫起來毛毛的(?)，原本感覺這樣作應該不會過，結果過了XD

首先其實每個人從哪邊進站哪邊出站是不重要的，可以看成每一站有好幾個人進去，最後每一站也有好幾個人出來，因為用題目說的交換方法的話可以任意互換兩個人的起點(前提是他們有交集)。所以問題就變成：在長度為 n 的環上，有 m 個入口 m 個出口(都可以在同個位置)，現在要幫每個入口找到一個出口根他配對，使得 sigma ( 入口到出口的距離 ) 最小。

我想到這裡第一個就想到二分圖最大權匹配，但題目的規模沒辦法作，所以卡了很久......後來想到如果對每個入口都選離他最近的出口，選完後把被選到的出口拔掉，這樣不知道會不會過，我在想證明的時候雖然是好像有證出來，可是還是覺得怪怪的XD

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10 ;
 
multiset<int> s1,s2 ;
 
main()
{
    int n,m ;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int s=0 ;
        s1.clear() ; s2.clear() ;
        while(m--)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            s1.insert(x) ;
            s2.insert(y) ;
            s+= x>y ? y-x+n : y-x ;
        }
        while(!s1.empty())
        {
            int x=*s1.begin() ; s1.erase(s1.find(x)) ;
            auto it=s2.lower_bound(x) ;
            if(it==s2.end()) it=s2.begin() ;
            s-= x>*it ? *it-x+n : *it-x ;
            s2.erase(it) ;
        }
        printf("%d\n",s) ;
    }
}