首页 > 代码库 > HDU 1051 Wooden Sticks
HDU 1051 Wooden Sticks
http://acm.hdu.edu.cn/showproblem.php?pid=1051
题意:
给定n根木条的长度l和重量w
从1min开始,每次处理长度为l重量为w的木条后,处理l‘>=l且w‘>=w的木条不费时间,否则+1min
求处理全部木条所需的最短时间
解法:
贪心法
将木条按长度l和重量w升序排序
从第一个未标记的木条开始,往后扫一遍将第一个满足w‘>=w的木条进行标记,直到所有木条被标记
则扫的次数就是最短时间
代码: 0MS 1100K
#include <cstdio>#include <algorithm>using namespace std;#define N 5000struct Stick { int l, w;} s[N];bool vis[N];bool cmp(Stick a, Stick b) { return a.l < b.l || a.l == b.l && a.w < b.w;}int main() { int t, n, ans; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", &s[i].l, &s[i].w); vis[i] = 0; } sort(s, s + n, cmp); ans = 0; for (int i = 0; i < n; i++) { if (!vis[i]) { for (int j = i + 1, mn = s[i].w; j < n; j++) { if (!vis[j] && s[j].w >= mn) { mn = s[j].w; vis[j] = 1; } } ans++; } } printf("%d\n", ans); } return 0;}
HDU 1051 Wooden Sticks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。