zoj3888 找第二大

题目简化后最终要求的就是第二大的数。但是由于数据较大，不能直接求。可以先预处理，求出所有情况。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct node

{

    int from;

    int to;

};

struct Node

{

    int max1;

    int max2;//di er ge

};

node a[];

int n,m,p,ans[];

bool cmp(node aa,node bb)

{

    if(aa.from!=bb.from)

    return aa.from>bb.from;

    return aa.to>bb.to;

}

int main()

{

    int i,j;

    while(scanf("%d%d%d",&n,&m,&p)!=EOF)

    {

        Node ret;

        memset(ans,,sizeof(ans));

        for(i=;i<m;i++)

            scanf("%d%d",&a[i].from,&a[i].to);

        sort(a,a+m,cmp);

        int count;

        ret.max1=ret.max2=;

        count=;

        j=;

        for(i=n;i>=;i--)//bian li nian

        {

            for(;j<m;j++)

            {

                if(a[j].from<i)

                    break;

                count++;

                int temp=a[j].to;

                if(temp<ret.max2)

                {

                    ret.max2=temp;

                    if(ret.max2<ret.max1)

                    {

                        int t=ret.max2;

                        ret.max2=ret.max1;

                        ret.max1=t;

                    }

                }

            }

            if(count>=)

            {

                if(i-ret.max2<)

                    ans[i]=;

                else

                ans[i]=i-ret.max2;

            }

        }

        while(p--)

        {

            int x;

            scanf("%d",&x);

            printf("%d\n",ans[x]);

        }

    }

}