HDOJ 1051 Wooden Sticks

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1051

贪心题,最终败在了qsort上。。。

把返回情况-1,0,1记成了只返回1和0.结果WA之。。。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Author: Tanky Woo
// Blog:    www.WuTianQi.com
#include <iostream>
#include <cstdlib>
using namespace std;
 
int nCase, n;
 
 
typedef struct stick{
    int l;
    int w;
}Stick;
 
Stick stick[5005];
 
 
int cmp(const void *arg1, const void *arg2)
{
    Stick *v1 = (Stick*)arg1;
    Stick *v2 = (Stick*)arg2;
    if(v1->l != v2->l)
        return v1->l - v2->l;
    else
        return v1->w - v2->w;
}
 
int Solve()
{
    qsort(stick+1, n, sizeof(Stick), cmp);
    Stick pre;
    int cnt = 0;
    for(int i=1; i<=n; ++i)
        if(stick[i].l != 0 && stick[i].w != 0)
        {
            pre = stick[i];
            stick[i].l = stick[i].w = 0;
 
            for(int j=i+1; j<=n; ++j)
                if(stick[j].l>=pre.l && stick[j].w>=pre.w)
                {
                    pre = stick[j];
                    stick[j].l = 0;
                    stick[j].w = 0;
                }
            cnt++;
        }
    return cnt;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> nCase;
    while(nCase--)
    {
        cin >> n;
        for(int i=1; i<=n; ++i)
            cin >> stick[i].l >> stick[i].w;
        cout << Solve() << endl;
    }
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1051 Wooden Sticks》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注