描述
C小加有一些木棒，它们的长度和质量都已经知道，需要一个机器处理这些木棒，机器开启的时候需要耗费一个单位的时间，如果第i+1个木棒的重量和长度都大于等于
第i个处理的木棒，那么将不会耗费时间，否则需要消耗一个单位的时间。因为急着去约会，C小加想在最短的时间内把木棒处理完，你能告诉他应该怎样做吗？
输入
第一行是一个整数T，表示输入数据一共有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
解题思路：（贪心算法 + 动态规划，就是求单调递减或递增子序列的个数）
1.首先将木棒排序，总体为l递减排序，若len相等，则weight递减。
2.对第i个木棒处理：选出单调递减子序列，并将单调递减子序列标记为true（使用过）。选出后，时间+1.进行第i+1个木棒的处理
代码如下：
#include <stdio.h> #include <string.h> int getMinTime(int len[], int weight[], int n) { int min = 0, i, j, t; bool exchange, used[5000]; int cur; memset(used, false, n); // 冒泡排序O(n^2) for(i = 0; i < n - 1; i++) { exchange = false; for(j = n - 1; j > i; j--) { if(len[j] > len[j - 1] || len[j] == len[j - 1] && weight[j] > weight[j - 1]) { t = len[j]; len[j] = len[j - 1]; len[j - 1] =t; t = weight[j]; weight[j] = weight[j - 1]; weight[j - 1] =t; exchange = true; } } if(!exchange) break; } for(i = 0; i < n; i++) { if(!used[i]) { cur = weight[i]; used[i] = true; for(j = i + 1; j < n; j++) { if(!used[j] && cur >= weight[j]) { used[j] = true; cur = weight[j]; } } min++; } } return min; } int main() { int t, n, i; int length[5000], weight[5000]; scanf("%d", &t); while(t--) { scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d%d", &length[i], &weight[i]); } printf("%d ", getMinTime(length, weight, n)); } return 0; }
分析：这里采用的是冒泡排序，时间复杂度为O(n^2)，可以直接使用库函数sort（时间复杂度为n*log2(n)），这时需要建立一个结构体，将len和weight作为一个整体结构对待，如下：
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; struct Node { int len; int weight; }node[5000]; bool cmp(Node a, Node b) { if(a.len == b.len) return a.weight > b.weight; return a.len > b.len; } int getMinTime(int n) { int min = 0, i, j; bool used[5000]; int cur; memset(used, false, n); // sort直接排序n*log2(n) sort(node, node + n, cmp); for(i = 0; i < n; i++) { if(!used[i]) { cur = node[i].weight; used[i] = true; for(j = i + 1; j < n; j++) { if(!used[j] && cur >= node[j].weight) { used[j] = true; cur = node[j].weight; } } min++; } } return min; } int main() { int t, n, i; scanf("%d", &t); while(t--) { scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%d%d", &node[i].len, &node[i].weight); } printf("%d ", getMinTime(n)); } return 0; }