[HOJ 282]Empire disruption

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

我們先來想想這種題目: 給定N條繩子的長度，每個詢問要求從這N繩子分別減一段出來拼成更長的繩子，但對於每一條繩子最長只能取L公分，請問最長能拼出多長的繩子？
我們可以用貪心的思想，先把繩子長度排序，然後對於每筆詢問使用二分搜找出第一個夠長的繩子，用前綴和算出「不夠長的繩子」的長度總和，再加上「夠長的繩子的數量」*長度限制L，就是答案了
這題可以轉換成以上題型，相鄰城市的間距代表繩子長度(所以有N-1條繩子)，x+y代表長度限制L，至於第一座城市前和最後一座城市後會佔領多少可以用最小值O(1)求出
所以我們就成功把這題做出來了！(?)

對了以下code是不同解法，有興趣者請參考(?)

code:

#include<cstdio>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
int M,N,Q,FRONT,BACK;
int ANS[100000];
priority_queue<int,vector<int>,greater<int> >GAP;
struct Query
{
    int l,r,idx;
    Query(){}
    Query(const int _l,const int _r,const int _i):l(_l),r(_r),idx(_i){}
};
multimap<int,Query>QUERY;
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d%d",&M,&N,&Q)==3)
    {
        if(true)
        {
            vector<int>s;
            for(int i=0,v;i<N;i++)scanf("%d",&v),s.push_back(v);
            sort(s.begin(),s.end());
            while(!GAP.empty())GAP.pop();
            for(int i=1;i<N;i++)GAP.push(s[i]-s[i-1]-1);
            FRONT=s[0]-1,BACK=M-s[N-1];
            s.clear(),vector<int>().swap(s);
        }
        QUERY.clear();
        for(int i=0,l,r;i<Q;i++)
        {
            scanf("%d%d",&l,&r);
            QUERY.insert(make_pair(l+r,Query(l,r,i)));
        }
        if(true)
        {
            int now=0;
            for(const auto &it:QUERY)
            {
                while(!GAP.empty()&&GAP.top()<=it.first)N+=GAP.top()-now,GAP.pop();
                N+=(int)GAP.size()*(it.first-now);
                now=it.first;
                const Query &q=it.second;
                ANS[q.idx]=N+min(FRONT,q.l)+min(BACK,q.r);
            }
        }
        for(int i=0;i<Q;i++)printf("%d\n",ANS[i]);
        break;
    }
    return 0;
}