탐욕 서열

제목: http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=517
그동안 계차 단속 을 벌 였 는데 이제 야 욕심 을 알 게 되 었 다.구간 오른쪽 점 을 정렬 하여 가능 한 한 오른쪽 점 에서 수 를 취한 다.데이터 가 비교적 작 으 니 n ^ 2 면 됩 니 다.

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <string>

#include <iostream>

using namespace std;

struct Node

{

	int l;int r;int val;

}node[11111];

int cmp(const Node &a,const Node &b)

{

	return a.r<b.r;

}

int main()

{

	int n,l,r,c;

	while(cin>>n){

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

			cin>>l>>r>>c;

			node[i].l=l;node[i].r=r;node[i].val=c;

		}

		sort(node,node+n,cmp);int ans=0;

		int vis[1111]={0};

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

			for(int j=node[i].l;j<=node[i].r;j++){

				if(vis[j]) node[i].val--;

			}

			int gg=node[i].val;

			for(int j=node[i].r;j>=node[i].l&&gg>0;j--){

				if(!vis[j]){

					vis[j]=1;ans++;gg--;

				}

			}

		}

		printf("%d
",ans);

	}

	return 0;

}