Hdu2037

Hdu2037 - 今年暑假不AC

题意：

在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少。

解法：

这其实就是一个大水题，一个非常简单明了的区间覆盖问题。

CODE：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define LL long long

#define N 1000100

struct node {

    int start,end;

} tim[N];

int n;

inline bool cmp(node a,node b) {

    return a.end < b.end;

}

int main() {

    while(1) {

        scanf("%d",&n);

        if(n == 0) break;

        for(int i = 1 ; i <= n ; i++)

            scanf("%d%d",&tim[i].start,&tim[i].end);

        sort(tim + 1,tim + n + 1,cmp);

        int date = 0,ans = 0;

        for(int i = 1 ; i <= n ; i++) {

            if(date <= tim[i].start) {

                date = tim[i].end;

                ans++;

            }

        }

        printf("%d\n",ans);//hdu上少打空格，不然会Presentation Error

    }

    //system("pause");

    return 0;

}

巴特西

Hdu2037

Hdu2037 - 今年暑假不AC

题意：

解法：

CODE：

最新文章

热门文章