# Wooden Sticks（贪心）问题解析

2018-03-10 10:00:17         来源：铭 の ブロゲ

## 题目描述

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l<=l’ and w<=w’. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

## 输入

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

## 源代码

```#include
using namespace std;
#include
#include
struct M {
int x, y;
};
bool Comp(const int &a, const int &b)
{
if (a != b)return a > b;
else return a > b;
}
int main()
{
vectorv(5000);
int m, n;
cin >> m;
for (int i = 0;i < m;i++)
{
cin >> n;
for (int j = 0;j < n;j++)
{
cin >> v[j].x >> v[j].y;
}
//数据处理
for (int j = 0;j < n - 1;j++)
{
for (int z = 0;z < n - 1 - j;z++)
{
if (v[z].x < v[z + 1].x)
{
swap(v[z], v[z + 1]);
}
else if (v[z].x == v[z + 1].x)
{
if (v[z].y < v[z + 1].y)
{
swap(v[z], v[z + 1]);
}
}
}
}//将数据按照长度优先，重量次之的顺序重新排列完毕
int ans = 1, example = v[0].y;
for (int i = 0;i < n - 1;i++)
{
if (example < v[i + 1].y)
{
ans += 1;
example = v[i + 1].y;
}
}//以重量为参考，example变量保存最大值，如果出现更大值，则赋给example，同时，ans++
cout << ans << endl;
}
}```