【欲張り】hdu 4415 Assassin’s Creed

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=4415
标题:ある専門家級の殺し屋、彼はm耐久度の武器とn個の敵を持っていて、1人の敵を殺すにはai点の耐久を消費する必要がありますが、彼の武器を得ることができて、彼の武器でbi個の他の敵を殺すことができて、この殺し屋は最大でどれだけの敵を殺すことができて、殺人が最も多い情況の下で最小消費の耐久度はいくらですか.
问题解:贪欲な问题は、敌をbiの値でゼロ(a集合)と非ゼロ(b集合)の2つの集合に分ける.
状況1:まずa集合を考えて、この集合に対して、私たちはその中の1つを殺すだけで、敵の武器を手に入れることで、より多くの耐久性を消費することなく、この集合のすべての人を滅ぼすことができます.そのため、私たちは自分の武器でこの集合の中で最も耐久性の少ない敵を殺し、この集合のすべての武器を手に入れた.次に、bセットをai値で小さいものから大きいものに並べて、aセットから得た武器でaiの代価の大きい敵を殺すことができます.この時点で敵が消滅したら、出力します.残りの敵がいる場合、我々はa集合の前に敵の武器で殺したものとb集合の残りの敵とを一緒に考察した.この場合、2つの状況がある:1)自分の武器でa集合の中原を殺して敵の武器で殺した中aiの代価が最小であり、同時にこの元の敵を殺した武器でb集合の残りのaiの代価の最大を殺すことができる.2)自分の武器でbを0の中でaが一番小さいものを殺す.
状況2:まずb集合を考慮し,b集合の敵を処理し,余分な耐久度があればa集合の敵を処理する.
最後の答えは2つの状況の結合です.
テストデータ:
4 3 5 4 1 5 1 7 7 2 1 2 2 4 0 5 2 1 2 1 1 5 0 5 0 5 0 5 7 3 2 4 1 5 0 6 0 7 0
Case 1:3 4 Case 2:0 0 Case 3:5 2 Case 4:5 7
コード:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
struct px
{
    int a,b;
} node;
vector<struct px> a,b;
bool cmp(const struct px &x,const struct px &y)
{
    return x.a<y.a;
}
int main()
{
    int tt;
    int x,y,n,m,ida,idb;
    scanf("%d",&tt);
    for(int cas=1; cas<=tt; ++cas)
    {
        int ans=0,bx=0,mm=0,mn=0,ansn=0;
        a.clear();
        b.clear();
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&node.a,&node.b);
            if(node.b!=0) a.push_back(node);
            else          b.push_back(node);
        }
        sort(a.begin(),a.end(),cmp);
        sort(b.begin(),b.end(),cmp);
        ida=0;
        idb=b.size()-1;
        for(int i=0; i<b.size(); ++i)
        {
            if(m-mn>=b[i].a)
            {
                ansn++;
                mn+=b[i].a;
            }
        }
        if(a.size()>0&&a[0].a<=m)
        {
            node=a[0];
            mm+=node.a;
            for(int i=0; i<a.size(); i++)
            {
                bx+=(a[i].b-1);
                ans++;
            }
            bx++;
        }
        if(a.size()>0&&a[0].a<=m-mn)
        {
            node=a[0];
            mn+=node.a;
            for(int i=0; i<a.size(); i++)
                ansn++;
        }
        for(; bx!=0&&idb>=0; --idb,--bx,++ans);
        if(idb<0)
        {
            if(ans>ansn) printf("Case %d: %d %d
",cas,ans,mm);
            else if(ans<ansn) printf("Case %d: %d %d
",cas,ansn,mn);
            else printf("Case %d: %d %d
",cas,ansn,mn>mm?mm:mn);
        }
        else
        {
			int i,j;
            for(i=1,j=0; i<a.size()&&j<=idb;)
            {
                if(a[i].a<=b[j].a)
                {
                    if(m>=a[i].a+mm)
                    {
                        mm+=a[i].a;
                        i++;
                        ans++;
                        idb--;
                    }
                    else break;
                }
                else
                {
                    if(m>=b[j].a+mm)
                    {
                        mm+=b[j].a;
                        ans++;
                        j++;
                    }
                    else break;
                }
			}
			for(;j<=idb;++j)
			{
                    if(m>=b[j].a+mm)
                    {
                        mm+=b[j].a;
                        ans++;
                        j++;
                    }
                    else break;
			}
            if(ans>ansn) printf("Case %d: %d %d
",cas,ans,mm);
            else if(ans<ansn) printf("Case %d: %d %d
",cas,ansn,mn);
            else printf("Case %d: %d %d
",cas,ansn,mn>mm?mm:mn);
        }
    }
    return 0;
}

ソース:http://blog.csdn.net/acm_ted/article/details/8010170