CodeForces#311 C. Arthur and Table

題意：

給出一個桌子，有n個腿，每個腿的長度是l，拆掉這條腿的花費是d，當最長的腿占腿總數大于其他腿的總數，那麼合法，問到達合法情況的最小代價。

解題思路：

首先根據長度排個序，然後枚舉每種長度作為最長長度。枚舉到目前長度時，相同長度不砍，把比目前長度大的全砍掉（這個比較容易維護），然後再看現在是否已經滿足條件，，不滿足則從前面費用小的開始砍，直到滿足為止。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>

#define LL long long
#define fir first
#define sec second
using namespace std;

int n;
LL num[233333],s[233333],maxl,cost,ans,sl[233333];
pair<LL,LL>leg[233333];
multiset<LL>q;
//priority_queue<LL,vector<LL>,greater<LL> >q;
LL gao[233333];

int main(){
    ans=(LL)2333333333333333;
    scanf("%d",&n);
    memset(sl,0,sizeof(sl));maxl=0;memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++){scanf("%I64d",&leg[i].fir);maxl=max(maxl,leg[i].fir);}
    for(int i=1;i<=n;i++)scanf("%I64d",&leg[i].sec);
    sort(leg+1,leg+1+n);
    for(int i=1;i<=n;i++){num[leg[i].fir]++;sl[leg[i].fir]+=leg[i].sec;}
    for(int i=1;i<=maxl;i++)s[i]=s[i-1]+sl[i];
    int j=1;
    for(int i=1;i<=maxl;i++){
        if(s[i]==s[i-1])continue;
        cost=0;
        while(leg[j].fir<i)j++;
        set<LL>::iterator it=q.end();
        if(!q.empty())it--;
        for(int k=1;k<=num[i]-1;k++){
            if(q.empty())break;
            cost+=*it;
            if(it==q.begin())break;
            it--;
        }
        cost=s[i-1]-cost;
        cost+=s[maxl]-s[i];
        ans=min(ans,cost);
        while(leg[j].fir==i){
            q.insert(leg[j].sec);
            if(j==n)break;
            j++;
        }
    }
    printf("%I64d\n",ans);
    return 0;
}