http://acm.nyist.net/JudgeOnline/problem.php?pid=236
心急的C小加
時(shí)間限制：1000 ms | 內(nèi)存限制：65535 KB
難度：4
描述
C小加有一些木棒惕虑，它們的長(zhǎng)度和質(zhì)量都已經(jīng)知道坟冲，需要一個(gè)機(jī)器處理這些木棒，機(jī)器開(kāi)啟的時(shí)候需要耗費(fèi)一個(gè)單位的時(shí)間溃蔫，如果第i+1個(gè)木棒的重量和長(zhǎng)度都大于等于第i個(gè)處理的木棒健提，那么將不會(huì)耗費(fèi)時(shí)間，否則需要消耗一個(gè)單位的時(shí)間伟叛。因?yàn)榧敝ゼs會(huì)私痹，C小加想在最短的時(shí)間內(nèi)把木棒處理完，你能告訴他應(yīng)該怎樣做嗎痪伦？
輸入
第一行是一個(gè)整數(shù)T(1<T<1500)侄榴，表示輸入數(shù)據(jù)一共有T組。
每組測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)N（1<=N<=5000）,表示有N個(gè)木棒网沾。接下來(lái)的一行分別輸入N個(gè)木棒的L癞蚕，W（0 < L ,W <= 10000），用一個(gè)空格隔開(kāi)辉哥，分別表示木棒的長(zhǎng)度和質(zhì)量桦山。
輸出
處理這些木棒的最短時(shí)間。
#include<cstdio>
#include<algorithm>
using namespace std;
struct Node
{
int l,w,vis;
bool operator <(const Node & t) const{
return (l<t.l)||((l==t.l)&&w<t.w);
}
}arr[5050];
int main(){
int t;
scanf("%d",&t);
while(t-- )
{
int n,a,b;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
arr[i].l=a;
arr[i].w=b;
arr[i].vis=0;
}
sort(arr+1,arr+1+n);
int sum=0;
for(int i=1;i<=n;i++)
{
if(arr[i].vis==0)
{
arr[i].vis=1;
int last=arr[i].w;
for(int j=i+1;j<=n;j++)
{
if((arr[j].vis==0)&&(arr[j].w>=last))
{
last=arr[j].w;
arr[j].vis=1;
}
}
sum++;
}
}
printf("%d\n",sum);
}
}
