HDU 5214 Movie (賽碼"BestCoder"杯中國大學生程序設計冠軍賽A題)

HDU 5214 Movie (賽碼"BestCoder"杯中國大學生程序設計冠軍賽A題)

五一有幸跟著老師去了一次杭電，求虐之行，坐等清華北大等巨巨AK全場，總結經驗，激勵前進！

【題目鏈接】click here~~

【題目大意】在多個不確定區間裡面，問能否選出三個互不相交的區間

【解題思路】

ps:當時是hjs敲題，敲完之後三個人都檢查了一遍，發現沒有問題,但是交上去卻CE了，後面於是各種調，各種錯誤，最後發現把取模去掉，直接判斷一下是否存在一個區間位於已經出來的區間中間且不交叉即可，悲劇。。。

【官方解題報告】首先我們考慮如何選擇最左邊的一個區間，假設最左邊的區間標號是i, 那選擇的另外兩個區間的左端點必定要大於Ri，若存在i之外的j, 滿足Rj 本題的取模值十分特殊，用unsigned int的自然溢出可以達到同樣的效果，時間復雜度O(N)

代碼：

#include 
using namespace std;
const int N=1e7+10;
const int inf=0x3f3f3f3f;
struct node
{
    unsigned int pre,last;
} Map[N];
int main()
{
    int T,n;
    unsigned int L1,R1,a,b,c,d,maxx,minn;
    bool flag;
    scanf("%d",&T);
    while(T--)
    {
        flag=false;
        cin>>n>>L1>>R1>>a>>b>>c>>d;
        maxx=0;
        minn=inf;
        Map[0].pre=L1;
        Map[0].last=R1;
        for(int i=1; iMap[i].last) swap(Map[i].pre,Map[i].last);//全部處理之後再交換！
            if(Map[i].pre>maxx) maxx=Map[i].pre;//左端點最大的區間作為最右邊的區間
            if(Map[i].lastminn)
            {
                puts("YES");
                flag=true;
                break;
            }
        }
        if(!flag) puts("NO");
    }
    return 0;
}