设为首页 加入收藏

TOP

uvalive 2322 Wooden Sticks(贪心)
2014-11-23 21:42:22 来源: 作者: 【 】 浏览:13
Tags:uvalive 2322 Wooden Sticks 贪心
题目大意:给出要求切的n个小木棍 , 每个小木棍有长度和重量,因为当要切的长度和重量分别大于前面一个的长度和重量的时候可以不用调整大木棍直接切割, 否则要进行调整。现在要求求出一个序列, 使得调整的次数最少, 输出调整的次数。
解题思路:将n个小木棍先按照 长度和重量的大小排序,然后按照顺序将小木棍分堆,可入堆的要求是长度和重量大于当前这个堆的长度和重量,入堆之后, 要将新的木棍的属性赋值个这个堆, 如果当前所有堆都没法放下这个木棍, 就得单独放成一个堆。最后的堆数就是要求的调整次数。
#include   
#include   
#include   
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;  
    else  
    return 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;  
}  


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇hdu 3658 How many words 下一篇ural 1869. New Year Cruise

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·【C语言】动态内存管 (2025-12-27 06:23:20)
·C语言中的内存管理 - (2025-12-27 06:23:16)
·C语言指南:C语言内 (2025-12-27 06:23:14)
·Redis on AWS:Elast (2025-12-27 04:19:30)
·在 Spring Boot 项目 (2025-12-27 04:19:27)