题意分析

题目背景

本题属于贪心算法与序列覆盖问题，描述如何通过优化木棍加工顺序来最小化木工机器的设置时间。关键在于理解设置时间的计算规则，并找到最优的木棍处理顺序。

核心问题

1. 设置时间规则：
   • 第一根木棍的设置时间为1分钟。
   • 若下一根木棍的长度和重量均不小于当前木棍，则无需额外设置时间；否则需增加1分钟。
2. 目标：找到最小总设置时间的加工顺序。

输入输出

• 输入：
  • $T$：测试用例数量。
  • 每个测试用例包含$n$（木棍数量）和$n$对$(l_i, w_i)$（长度和重量）。
• 输出：每个测试用例的最小设置时间。

解题思路

1. 问题转换

• 非递减子序列覆盖：
  将问题转化为寻找最少的非递减子序列（在长度和重量上），每个子序列对应一次设置时间。
  数学表达：
  设序列$S$为木棍集合，需划分$S$为最少子序列$\{S_1, S_2, \dots, S_k\}$，使得每个$S_i$满足$l_j \leq l_{j+1}$且$w_j \leq w_{j+1}$。
  最小设置时间$=k$。

2. 贪心策略

• 排序：
  按长度从大到小排序，长度相同时按重量从大到小排序。
  目的：确保后续处理时长度条件已满足，仅需关注重量。
• 贪心选择：
  每次从未处理的木棍中选取最轻的可行木棍（重量不小于当前子序列末尾），构建非递减子序列。

3. 算法流程

1. 输入处理：读取木棍数据，存储为结构体数组。
2. 排序：按长度和重量降序排序。
3. 子序列计数：
   • 初始化设置时间$ans=0$和已处理木棍数$s=0$。
   • 循环直到所有木棍被处理：
     • 每轮构建一个非递减子序列，$ans$增加1。
     • 遍历未处理木棍，选择重量满足条件的木棍加入当前子序列。

算法实现

代码框架

#include<bits/stdc++.h>
using namespace std;
const int N=5005;

struct node{
	int l,w;
}; 
bool cmp(const node &a, const node &b){
	if(a.l==b.l){
		return a.w>b.w;
	}
	return a.l>b.l;	    
}
int main(){
    int num;
	cin>>num;
	while(num--)
	{
		int n,dp[N]={0},vis[N]={0};
		struct node a[N];
		cin>>n;
    for(int i=1; i<=n; i++){
    	cin>>a[i].l>>a[i].w;
	} 
    sort(a+1,a+1+n,cmp);
    int s=0,ans=0,m;
    while(s<n){
    	ans++;
    	m=0x7fffffff;
    	for(int i=1; i<=n; i++){
    		if(vis[i]==0&&a[i].w<=m){
    			m=a[i].w;
    			vis[i]=1;
    			s++;
			}
		}
	}
	cout<<ans<<endl;
	 } 
	return 0;
}

关键步骤

1. 排序：确保长度降序，同长度时重量降序。
2. 子序列构建：
   • 每轮初始化$current_w$为最大值，选择重量不超过$current_w$的木棍。
   • 标记已选木棍，更新$current_w$为当前木棍重量。
3. 计数：每完成一个子序列，$ans$加1。

复杂度分析

• 时间：$O(T \cdot n \log n)$，其中排序占主导（$n \leq 5000$）。
• 空间：$O(n)$，存储木棍数据及访问标记。