Untitled
raw download clone
TEXT
views 34
,
size 3194 b
#include<stdio.h>

int pos[5001]= {0},L[5001],R[5001],pos1[5001]= {0};
/*拆成三個CASE
無用的人0個1個跟2個以上
pos是i位置幾個衛兵守
pos1是衛兵編號i有幾個pos=1
who_pos是i位置最後是衛兵編號j踩到
*/
int who_pos[5001];
int Min(int x,int y);



int main(void)
{
    int t;
    int n,q,poop=0,all_q=0,min=5001,temp;
    /*
    poop無用之人數
    */

    scanf("%d",&t);
    while(t--)
    {

        scanf("%d%d\n",&n,&q);
        for(int i=1; i<=q; i++)
        {
            scanf("%d%d",&L[i],&R[i]);
            for(int j=L[i]; j<=R[i]; j++)
            {
                pos[j]++;
            }
        }

        for(int i=1; i<=n; i++) //全上可守衛區域
        {
            all_q+=(pos[i]>0);
        }
        for(int i=1; i<=q; i++) //找無用的人
        {
            int j;
            for(j=L[i]; j<=R[i]; j++)
            {
                if(pos[j]<=1)
                    break;
            }
            if(j==R[i]+1)
            {
                poop++;
                temp=i;
                for(int i=L[temp]; i<=R[temp]; i++)
                {
                    pos[i]--;
                    //拔掉那個無用的
                }
            }

        }
        for(int i=1; i<=q; i++)
        {
            if(i!=temp)
            {
                for(int j=L[i]; j<=R[i]; j++)
                {
                    who_pos[j]=i;//每個位子最後站誰
                }
            }
        }
        if(poop>1)//直接拔掉2個無用
        {
             printf("%d\n",all_q);
             //printf("temp= %d\n",temp);
        }
        else if(poop==1)//一個無用找剩下最小pos1
        {
            for(int i=1; i<=n; i++)
            {
                if(pos[i]==1)
                {
                    pos1[who_pos[i]]++;
                }
                //找到第i士兵只有他可以守的位子數
            }
            pos1[temp]=5001;
            for(int i=1; i<=q; i++)
            {
                min=Min(min,pos1[i]);
            }
            printf("%d\n",all_q-min);
        }
        else
        {
            for(int i=1; i<=n; i++)
            {
                if(pos[i]==1)
                    pos1[who_pos[i]]++;
                //找到第i士兵只有他可以守的位子數
            }
            //找最小的兩個pos1
            min=5001;
            for(int j=1; j<=q; j++)
            {
                min=Min(min,pos1[j]);
                if(pos1[j]==min)
                    temp=j;

            }
            pos1[temp]=5001;
            temp=5001;
            for(int i=1; i<=q; i++)
            {
                temp=Min(temp,pos1[i]);
            }
            printf("%d\n",all_q-min-temp);

        }

        for(int i=1; i<=n; i++)
        {
            pos[i]=0;
            pos1[i]=0;
            who_pos[i]=0;
        }
        min=5001;
        poop=0;
        all_q=0;
        temp=0;

    }

    return 0;
}
int Min(x,y)
{
    if(x<y)
        return x;
    else
        return y;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.