Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

　有一个整数序列，我们不知道她的长度是多少（即序列中整数的个数），但我们知道在某些区间中至少有多少个整数，用区间

[ai,bi,ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。现在给出若干个这样的区间，

请你求出满足条件的最短序列长度是多少。如果不存在则输出 -1。

【输入格式】

第一行包括一个整数n(n<=1000)，表示区间个数；

　 以下n行每行描述这些区间，第i+1行三个整数ai，bi，ci，由空格隔开，其中0<=ai<=bi<=1000 而且 1<=ci<=bi-ai+1。

【输出格式】

文件输出只有一个整数表示满足要求序列长度的最小值。

Sample Input

5

3 7 3

8 10 3

6 8 1

1 3 1

10 11 1

Sample Output

6

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t081

【题解】



先把n个ai,bi,ci按照ai第一关键字,bi第二关键字升序排;

然后逆序处理n个关系;

优先选ai..bi这个区间里面的前面部分(当然如果这个区间里面有些数字已经被选了就不用再选了),这样优先选前面的部分,就能让前面的关系更容易利用公共的部分;就是这样的贪心吧.

转换成编程语言就是升序枚举啦^_^

(想不出来什么情况会无解..)



【完整代码】

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 1000+100;

struct abc

{

    int a,b,c;

    friend bool operator < (abc x,abc y)

    {

        if (x.a==y.a)

        {

            if (x.b==y.b)

                return true;

            else

                return x.b<y.b;

        }

        else

            return x.a < y.a;

    }

};

int n;

bool bo[MAXN];

abc t[MAXN];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    scanf("%d",&n);

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

        scanf("%d%d%d",&t[i].a,&t[i].b,&t[i].c);

    sort(t+1,t+1+n);

    for (int i = n;i >= 1;i--)

    {

        for (int j = t[i].a;j <= t[i].b;j++)

            if (bo[j])

            {

                t[i].c--;

                if (t[i].c==0)

                    break;

            }

        if (t[i].c!=0)

        {

            for (int j = t[i].a;j <= t[i].b;j++)

                if (!bo[j])

                {

                    t[i].c--;

                    bo[j] = true;

                    if (t[i].c==0)

                        break;

                }

        }

    }

    int si = 0;

    for (int i = 0;i <= 1000;i++)

        if (bo[i])

            si++;

    printf("%d\n",si);

    return 0;

}