宁夏邀请赛H

题意：

一个人去打n只怪兽，每只怪兽有HP值和ATK值，分别表示血量与对人造成的伤害，每次打的时候活着的所有怪兽都会对人造成伤害，对于一只怪兽来说，人第i次打它HP下降i。问人打完所有怪兽受到的最小伤害为多少。

思路：

打的次数事实上与HP并不是正相关的，所以要先算出每只怪兽要打几次。

考虑两只怪兽的时候，设打的次数分别为h1和h2，ATK值分别为a1和a2，要使先打第一只怪兽受到的伤害比较小，则有h1(a1+a2)+h2a2<h2(a1+a2)+h1a1，化简后变成h1/a1<h2/a2。

所以要按打的次数/ATK值从小到大排序。

代码：

typedef long long ll;
struct node
{
    ll hp,atk;
    double val;
}a[100010];
ll suf[100010];
ll f[100010];
bool cmp(node x,node y)
{
    return x.val<y.val;
}
int init()
{
    int num;
    f[1]=1;
    for(int i=2;;i++)
    {
        ll temp=(ll)i;
        f[i]=temp*(temp+1)/2;
        if(f[i]>=100000)
        {
            num=i;
            break;
        }
    }
    /*for(int i=1;i<=num;i++)
        printf("%lld ",f[i]);
    printf("\n");*/
    return num;
}
int main()
{
    int t,n,num;
    scanf("%d",&t);
    num=init();
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&a[i].hp,&a[i].atk);
            int pos=lower_bound(f+1,f+num+1,a[i].hp)-f;
            a[i].hp=pos;
            a[i].val=1.0*a[i].hp/a[i].atk;
        }
        sort(a+1,a+n+1,cmp);
        suf[n+1]=0;
        for(int i=n;i>=1;i--)
            suf[i]=suf[i+1]+a[i].atk;
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans+=a[i].hp*suf[i];
        printf("Case #%d: %lld\n",kase,ans);
    }
    return 0;
}
计蒜之道复赛A

题意：

给你n个一次函数，给出一个x，让你嵌套成一次函数的形式，一次函数可以任意改变顺序，求的最大值。

思路：

同样是考虑两个变量的时候，设有，要使，化简得到。所以按从小到大排序，从里到外计算即可。

代码：

struct node
{
    int a,b;
}num[10010];
bool cmp(node x,node y)
{
    return 1.0*(1-x.a)/x.b>1.0*(1-y.a)/y.b;
}
int main()
{
    int t,n,x;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&x);
        for(int i=0;i<n;i++)
            scanf("%d",&num[i].a);
        for(int i=0;i<n;i++)
            scanf("%d",&num[i].b);
        sort(num,num+n,cmp);
        int ans=x;
        for(int i=0;i<n;i++)
        {
            ans=((ans*num[i].a)+num[i].b)%10;
            //printf("%d\n",ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}
总结

这两道题目都是从两项入手算出来的，而且这种条件是传递的。这是考虑贪心问题的一种方向。