题目描述
某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若 i<j，则 Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组？
输入
第一行为一个整数 N（N<=1000），表示零件的个数，第二行有 N 对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过 10000。
输出
仅一行，即最少分成的组数。
样例输入
5
8 4 3 8 2 3 9 7 3 5
样例输出
2
分析：首先每一组必须满足两个条件，零件的长度和重量都是不下降的。如果同时考虑这两个条件的话，会比较麻烦，所以好的思想是先简化条件。
那么我们可以先按长度从小到大排序，然后按这个顺序给零件分组。这样每一组零件的长度一定是不下降的，只用考虑重量即可。
那关于重量该怎么处理呢？首先可定的是，如果当前的零件的重量小于该组最后一个零件的重量的话，那一定不能放在这一组了，必须放到另一个合法的组（或者新成立一组）。
但如果这个零件可以放到这一组呢？是直接放吗？那可不一定，比如下图
还有(6, 7) 和 (7, 5) 没有放，如果(6, 7) 放到第一组的话，那么(7, 5) 就必须新开一组了。但是最优的方法是(6, 7) 放到第二组，(7, 5) 放到第一组，这样总共就两组。
所以对于每一个零件，我们要放到重量和他最相近（但不能大于它）的零件上面，保证放完这个零件后所浪费的空间最少。（空间只是为了好说话，并不是严格意义上的空间）
具体代码的实现，因为题中说长度和重量均不超过 10000，那么就可以开一个数组记录每一组的最后一个零件的重量。然后对于每一个零件 i，从 w[i] 开始向 0 循环，若遇到一个vis[j] 被标记过，说明这有一组，且放完后浪费的空间一定最少，就 vis[j] --, vis[w[i]] ++, break，表示这一组的最后一个零件的重量变成了 w[i]。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 #define rep(i, a, n) for(int i = a; i <= n; ++i) 8 #define per(i, n, a) for(int i = n; i >= a; --i) 9 typedef long long ll; 10 const int maxn = 1e3 + 5; 11 const int max_num = 1e4 + 5; 12 13 struct Node 14 { 15 int l, w; 16 bool operator < (const Node& other)const 17 { 18 return (l < other.l) || (l == other.l && w <= other.w); 19 } 20 }a[maxn]; 21 int n, vis[max_num]; 22 int ans = 0; 23 int main() 24 { 25 freopen("stick.in", "r", stdin); 26 freopen("stick.out", "w", stdout); 27 scanf("%d", &n); 28 rep(i, 1, n) scanf("%d%d", &a[i].l, &a[i].w); 29 sort(a + 1, a + n + 1); 30 rep(i, 1, n) 31 { 32 per(j, a[i].w, 0) 33 if(vis[j]) {vis[j]--; break;} 34 vis[a[i].w]++; 35 } 36 rep(i, 1, max_num - 1) if(vis[i]) ans++; //数一数有多少组 37 printf("%d ", ans); 38 return 0; 39 }