首页 / 算法 / HD-ACM算法专攻系列（21）——Wooden Sticks

HD-ACM算法专攻系列（21）——Wooden Sticks

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HD-ACM算法专攻系列（21）——Wooden Sticks，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含969字，纯文字阅读大概需要2分钟。

内容图文

题目描述：

技术分享

技术分享

 

AC源码：

此题考查贪心算法，解题思路：首先使用快速排序，以w或l按升序排序（注意相等时，应按另一值升序排序），这样就将二维变量比较，变为了一维的，排好序的一边就不需要去管了，只需要对未排序的一边直接进行贪心遍历。时间复杂度O(n^2)

#include"iostream"
#include"algorithm"
using namespace std;

struct Stick
{
    int l;
    int w;
    bool processed;
};

bool cmp(Stick a, Stick b)
{
    
    if(a.l < b.l)
    {
        return true;
    }
    else if(a.l == b.l)
    {
        return a.w < b.w;
    }
    else
    {
        return false;
    }
}

int main()
{
    int t, n, total, val;
    Stick s[5000];
    scanf("%d", &t);
    for(int i = 0; i < t; i++)
    {
        scanf("%d", &n);
        total = 0;
        for(int j = 0; j < n; j++)
        {
            scanf("%d %d", &s[j].l, &s[j].w);
            s[j].processed = false;
        }
        sort(s, s+n, cmp);
        for(int j = 0; j < n; j++)
        {
            if(!s[j].processed)
            {
                total++;
                val = s[j].w;
                s[j].processed = true;
                for(int k = j + 1; k < n; k++)
                {
                    if(!s[k].processed && s[k].w >= val)
                    {
                        val = s[k].w;
                        s[k].processed = true;
                    }
                }
            }
        }
        printf("%d\n", total);
    }
    return 0;
}

原文：http://www.cnblogs.com/forcheng/p/7634905.html

内容总结

以上是互联网集市为您收集整理的HD-ACM算法专攻系列（21）——Wooden Sticks全部内容，希望文章能够帮你解决HD-ACM算法专攻系列（21）——Wooden Sticks所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1283543.html

来源：【匿名】