游客 Signup | Login
中文 | En

3488 - 约会

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

狗娃有一些木棒，它们的长度和质量都已经知道，需要一个机器处理这些木棒，机器开启的时候需要耗费一秒的时间，如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒，那么将不会耗费时间，否则需要消耗一秒的时间。因为急着和女朋友约会，狗娃想在最短的时间内把木棒处理完，聪明的你能告诉他应该怎样做吗？
 

Input

第一行是一个整数T(1<T<1500)，表示输入数据一共有T组。
 每组测试数据的第一行是一个整数N（1<=N<=5000）,表示有N个木棒。接下来的N行分别输入N个木棒的L，W（0 < L ,W <= 10000），分别表示木棒的长度和质量。

Output

处理这些木棒的最短时间。

Examples

Input Format

3 
5 
4 9 
5 2 
2 1 
3 5 
1 4 
3 
2 2 
1 1 
2 2 
3 
1 3 
2 2 
3 1

Output Format

2
1
3

Solution C++

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct fun
{
    int length;
    int weight;
} s[5010];
int cmp(fun a,fun b)
{
    if(a.length!=b.length)
        return a.length<b.length;
    else
        return a.weight<b.weight;
}
int main()
{
    int n,m,count,end,j;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    while(n--)
    {
        count=0;
        cin>>m;
        for(int i=0; i<m; i++)
            cin>>s[i].length>>s[i].weight;
        sort(s,s+m,cmp);
        for(int i=0; i<m; i++)
        {
            end=s[i].weight;
            if(s[i].weight!=0)
            {
                for(j=i+1; j<m; j++)
                    if(s[j].weight>=end)
                    {
                        end=s[j].weight;
                        s[j].weight=0;
                    }
                count++;
            }

        }
        cout<<count<<endl;
    }
}
请先登陆