题目描述
有一堆 n 根木棍。每根棍子的长度和重量都是预先知道的。这些木棍将由木工机器以一种方式进行加工。机器准备加工一根棍子需要一些时间,称为设置时间。设置时间与机器中的清洁操作和更换工具和形状有关。木工机器的设置时间如下:
(a) 第一根木棒的设置时间为 1 分钟。
(b) 在加工长度为 l 且重量为 w 的木棍后,如果 l <= l’ 和 w <= w’,机器将不需要设置时间来处理长度为 l’ 和重量 w’ 的木棍。否则,设置需要 1 分钟。
你要找到处理给定一堆 n 根木棍的最短准备时间。例如,如果您有五根长度和重量对分别为 (9 , 4 ) 、 ( 2 , 5 ) 、 ( 1 , 2 ) 、 ( 5 , 3 ) 和 ( 4 , 1 ) 的棍子,那么最小设置时间应该是 2 分钟,因为有一系列对 (4, 1), (5, 3), (9, 4), (1, 2), (2, 5)。
输入:
输入由 T 个测试用例组成。测试用例的数量(T)在输入文件的第一行给出。每个测试用例由两行组成:第一行有一个整数 n , 1 <= n <= 5000 ,表示测试用例中木棍的数量,第二行包含 2n 个正整数 l1 , w1 , l2 , w2 ,…, ln , wn ,每个数量级最多为 10000 ,其中 li 和 wi 分别是第 i 根木棍的长度和重量。2n 个整数由一个或多个空格分隔。
输出:
输出应包含以分钟为单位的最短设置时间,每行一个。
样例
输入:
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
(贪心)
有点类似拦截导弹,只不过每一个导弹没有固定的顺序;用pair存l , w,直接排序;然后枚举每一块木头,因为是先按左端点排序,所以枚举每一块木头时,此时的左端点一定大于等于前面所有左端点,所以只需要考虑右端点是否大于前面的即可,再根据贪心的思想,将当前木头放在能放的最大的w木头后面才能使答案最优,此时可以用一个一维temp数组存储每个系列的最后的木头的w,可以分析得到temp数组一定是单调递减的,所以枚举木头时只需从后往前遍历temp数组,找到第一个严格大于当前木头的右端点的木头,将当前木头放在它的后面.特别的,如果当前木头小于temp的末尾,则系列+1
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;
typedef long long LL ;
typedef pair<int,int> PII ;
const int N = 5010 ;
PII stick[N] ;
int temp[N] ;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t ;
cin >> t ;
while(t--)
{
int n;
cin >> n ;
for(int i = 1 ; i <= n ; i++) cin >> stick[i].first >> stick[i].second ;
sort(stick + 1 , stick + 1 + n) ;//按左右端点从小到大
int cnt = 1 ;//记录序列个数
temp[1] = stick[1].second ;//记录右端点值,单调递减,左端点无意义,优化成一维数组
for(int i = 2 ; i <= n ; i++)
{
int j = cnt ;
while(j >= 1 && temp[j] <= stick[i].second) j-- ;//枚举右端点,因为左端点已经排过序,所以没有意义了
if(j == cnt) temp[++cnt] = stick[i].second ;//比末尾还小,开一个新序列
else temp[j + 1] = stick[i].second ;
}
cout << cnt << endl ;
}
return 0 ;
}