这样的贪心策略不对么?
  • 板块P1233 木棍加工
  • 楼主Star·
  • 当前回复3
  • 已保存回复3
  • 发布时间2017/4/16 16:16
  • 上次更新2025/8/5 16:12:58
查看原帖
这样的贪心策略不对么?
35869
Star·楼主2017/4/16 16:16
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,t1=1,t2=1,ans=0,lmax,wmax;
struct woodenstick
{
    int l;
    int w;
};
struct woodenstick s[10000];
struct woodenstick wo[10000];
int cmp1(woodenstick a,woodenstick b)
{
    if(a.l==b.l) return a.w>b.w;
    return a.l>b.l;
}
int cmp2(woodenstick a,woodenstick b)
{
    if(a.w==b.w) return a.l>b.l;
    return a.w>b.w;
}
int main()
{
    scanf("%d",&n);
    if(n==0) 
    { 
        printf("0\n");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&s[i].l,&s[i].w);
        wo[i].l=s[i].l;
        wo[i].w=s[i].w;    
    }
    sort(s+1,s+1+n,cmp1);
    sort(wo+1,wo+1+n,cmp2);
    wmax=s[1].w;
    for(int i=2;i<=n;i++)
    {
        if(s[i].w<=wmax)
        {
            wmax=s[i].w;
            continue;
        }
        wmax=s[i].w;
        t1++;
    }
    lmax=wo[1].l;
    for(int i=2;i<=n;i++)
    {
        if(wo[i].l<=lmax)
        {
            lmax=wo[i].l;
            continue;
        }
        lmax=wo[i].l;
        t2++;
    }
    ans=min(t1,t2);
    //printf("%d %d ",t1,t2);
    printf("%d",ans);
    return 0;
}
2017/4/16 16:16
加载中...