本文主要是介绍uvalive 2322 Wooden Sticks(贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：2322 Wooden Sticks
题目大意：给出要求切的n个小木棍 ， 每个小木棍有长度和重量，因为当要切的长度和重量分别大于前面一个的长度和重量的时候可以不用调整大木棍直接切割， 否则要进行调整。现在要求求出一个序列， 使得调整的次数最少， 输出调整的次数。
解题思路：将n个小木棍先按照 长度和重量的大小排序，然后按照顺序将小木棍分堆，可入堆的要求是长度和重量大于当前这个堆的长度和重量，入堆之后， 要将新的木棍的属性赋值个这个堆， 如果当前所有堆都没法放下这个木棍， 就得单独放成一个堆。最后的堆数就是要求的调整次数。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 5005;struct stick {int len;int wei;
}tmp[N], rec[N];bool cmp(const stick& a, const stick& b) {if (a.len != b.len)return a.len < b.len;elsereturn a.wei < b.wei;
}int main() {int cas, n, cnt, begin;scanf("%d", &cas);while (cas--) {cnt = 0;memset(tmp, 0, sizeof(tmp));memset(rec, 0, sizeof(rec));scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d %d", &tmp[i].len, &tmp[i].wei);sort(tmp, tmp + n, cmp);for (int i = 0; i < n; i++) {int flag = 1;for (int j = 0; j < cnt; j++) {if (tmp[i].len >= rec[j].len && tmp[i].wei >= rec[j].wei) {rec[j] = tmp[i];flag = 0;break;}}if (flag) rec[cnt++] = tmp[i];}printf("%d\n", cnt);}return 0;
}
这篇关于uvalive 2322 Wooden Sticks(贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
