南阳理工OJ 236 心急的C小加 两个条件限制贪心

  连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=236

 

心急的C小加

时间限制：1000 ms  |  内存限制：65535 KB

难度：4

 

描述

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

 

输入

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

输出

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

样例输入

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 

样例输出

2
1
3

 

/*
用贪心的方法写的，先对数据进行双重排序，把第i个数据放入动态数组
的过程是：先和前面放在动态数组的数比较，如果没有一个小于这个数
，就放在动态数组的后面，表示需要加一个单位时间来做这根木棒，
如果有比这个数小的，就找出他们长度就接近的，也就是相差最小的数，
用这第i个数覆盖它，以此类推。。。最后动态数组的长度就是最少所需要的时间
*/
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
       int x;
       int y;
}p[1005];
bool operator < (const node a,const node b)//双重排序
{
       if(a.x == b.x)return a.y < b.y ;
       return a.x < b.x;
}
vector<int> time;
vector<int>::iterator it,maskit;
int main()
{
       int T,i,n,f,min;
       scanf("%d",&T);
       while(T--)
       {
              scanf("%d",&n);
              for(i=0;i<n;i++)
                     scanf("%d%d",&p[i].x,&p[i].y);
              sort(p,p+n);
              for(i=0;i<n;i++)
              {
                     f=0;min=1<<30;
                     for(it=time.begin();it!=time.end();it++)//和动态数组前面的数比较
                            if(p[i].y>=*it&&p[i].y-*it<=min)
                                   {min=p[i].y-*it;maskit=it;f=1;}
                     if(f==0)time.push_back(p[i].y);//如果没有比它小的就放在后面
                     else *maskit+=min;  //找到了就把就接近它的数更新一下
                    /* for(it=time.begin();it!=time.end();it++)printf("%d  ",*it);
                     printf("\n");*/
              }
              printf("%d\n",time.size());
              time.clear();
       }
       return 0;
}

 

 刚才的代码  很直观，但效率不太高，

下面来个效率高的（做题思想是一样的）

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct mb
{
	int len;//**长**//
	int weight;//**重量**//
}w[10001];
bool comp(mb x,mb y)//**按照长度排序，如果长度相同则按重量排序**//
{
	if(x.len<y.len) return true;
	if(x.len==y.len&&x.weight<y.weight) return true;
	return false;
}
int main()
{
	int s,n,i,j,count,t;
	scanf("%d",&s);
	while(s--)
	{
		memset(w,0,sizeof(w));//**首先需要将数组清零**//
		count=0;
		scanf("%d",&n);
		for(i=0;i<=n-1;i++)
		{
			scanf("%d %d",&w[i].len,&w[i].weight);
		}
		sort(w,w+n,comp);
		for(i=0;i<=n-1;i++)//**此时长度、重量已经从小到大排好了**//
		{
			if(w[i].weight!=0)//**如果这个数没有出现过，后面代码有标记**//
			{
				t=w[i].weight;
				count++;
				for(j=i+1;j<=n-1;j++)
				{
					if(w[j].weight>=t)
					{
						t=w[j].weight;//**用一个数保存最新清零的重量，在j循环中保证了一次能够处理的木棒最多**//
						w[j].weight=0;//**将排好序的标记为0，清除**//
					}
				}
			}
		}
		printf("%d\n",count);
	}
	return 0;
}