Blog·Tanky WooABOUTRSS

HDOJ 1051 Wooden Sticks

12 Jan 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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

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

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

AC代码:

// Author: Tanky Woo
// Blog:    www.WuTianQi.com
#include 
#include 
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;
    }
}