杭电1051~Wooden Sticks

杭电1051~~Wooden Sticks

这一题，典型的贪心，题目意思很容易看懂，加工木块，计算设置木块的时间，后面的木块重量和长度都大于等于前面的，就可以不用重新设置，但按长度排序或重量排序，按从大到小或从小到大都可以。这一点大家想想为什么。

这里我用的是长度来排序，长度相同的，按重量来排序。

一开始我是这么想的，排好序之后，从中找到可以一次消掉最多木块的一组，这样一直消下去，但是，很可惜，超时了。后来想想，没有必要去找，直接从前往后找，符合的木块直接消掉，因为，结果都是一样的，可以很容易的想明白的。对吧？？只是消的顺序变了而已。明白了吧。

下面是AC的代码：

# include <iostream>
# include <algorithm>
using namespace std;

class wooden
{
public:
	int length, weight;
	int flag;
};
bool cmp(const wooden &a, const wooden &b)   //排序
{
	if(a.length!=b.length)  
        return a.length > b.length;
    else  
        return a.weight > b.weight;
}
int main()
{
	int t;
	int finds(wooden *p, int n);
	int is_empty1(wooden *p, int n);
	cin >> t;
	while(t--)
	{
		int n, i, time = 0;
		cin >> n;
		wooden *p = new wooden[n];
		for(i = 0; i < n; i++)
		{
			cin >> p[i].length >> p[i].weight;
			p[i].flag = 0;
		}
	    sort(p, p + n, cmp);          //排序
		for(i = 0; i < n; i++)       //从前往后找符合的，flag标记为1
		{
			if(p[i].flag)
				continue;
			int min = p[i].weight;
			for(int j = i + 1; j < n; j++)
			{
				if(min >= p[j].weight && !p[j].flag)
				{
					min = p[j].weight;
					p[j].flag = 1;
				}
			}
			time++;                  //一次结束后，时间+1
		}
		cout << time << endl;
		delete []p;
	}
	return 0;
}

这题相对简单，但也蛮经典的！~~