题解 P1496 【火烧赤壁】

2017-02-28 21:41:02


和楼下的都是离散,写法有点不同,但好像没有打C++的

就是将每一个点离散一下,简单来说就是排序,排序时用每一个线段开始的点从小到大排

排序后所以点就在一个线段上,然后先记录下第一个点的开始和结束,往后面的点枚举,并继续判断

1.如果当前点为开始点且小于记录的结束点,就不管它继续往后枚举

2.如果当前点为开始点且大于记录的结束点,直接放弃记录的值,将当前的开始结束替换掉原先记录的值,并将原先记录的值的结束减去开始来累加ans

3.对于全部的结束点,如果大于记录的结束点直接替换,如果小于就不管它,继续向后枚举

楼下的pascal说要开int64

这里C++可以不用开long long

#include <stdio.h>
#include <algorithm>
#define max(x,y) x>y?x:y //离散时比较大小的函数
using namespace std;
struct arr
{
    int x,y;
};
arr a[30001];
int cam(arr a,arr b) //从小到大离散化
{
    return a.x<b.x;
}
int main()
{
    int n,m,p;
    scanf("%d",&n);
    if (p+1<m) m=p+1;
    for (int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i].x=x;
        a[i].y=y;
    }
    sort(a+1,a+n+1,cam); //离散
    int begin=a[1].x,end=a[1].y,ans=0,ans1=a[1].y-a[1].x;
    for (int i=2;i<=n;i++) //记录开始和结束的位置
    {
        if (a[i].x<=end) //每到一个点判断它是否在结束位置之前
        {
            if (a[i].y>end)
                end=a[i].y;
        }
        else 
        {
            ans+=end-begin;
            begin=a[i].x;
            end=a[i].y;
        }
    }
    ans+=end-begin;
    printf("%d\n",ans);
}