自动搬运

查看原文

来自洛谷，原作者为

	communist Who Dare Wins !

搬运于2025-08-24 21:45:25，当前版本为作者最后更新于2018-09-14 20:53:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到没有完整的贪心题解，本蒟蒻决定来补充一发（没有完整证明的贪心是不圆满的）

不知道大家做过$NOIP2012$国王游戏没，这两道题思路相似

进入正题，看着就像贪心的一道题

怎么贪，按$height,strength,weight$排序好像都不合适

试图分析相邻两项交换的影响

一个$\text{\red{位置}}$的承重量可以这样表示$Rest_i=Strength_i-\sum{Weight_j}(j>i)$

同理，它的下一项可以如下表示$Rest_{i+1}=Strength_{i+1}-\sum{Weight_j}(j>i+1)$

相邻两项交换后是这样的

$Rest_i=Strength_{i+1}-Weight_i-\sum{Weigth_j}(j>i+1)$

$Rest_{i+1}=Strength_i-\sum{Weight_j}(j>i+1)$

我们要使稳定强度最大，即最大化$Min(Rest_i)$

还是考虑这相邻两项，我们考虑是否交换就转化为了判断这个东西

$max(min(PreRest_i,PreRest_{i+1}),min(NextRest_i,NextRest_{i+1}))$

为了简化式子

我们给上述每项同加$\sum{Weight_j}(j>i+1)$

上式化简为

$max((Pre)min(Strength_i-Weight_{i+1},Strength_{i+1}),(Next)min(Strength_{i+1}-Weight_i,Strength_i))$

观察到

$Strength_i>=Strength_i-Weight_{i+1},Strength_{i+1}>Strength_{i+1}-Weight_i$

如果

$Strength_{i+1}-Weight_i<=Strength_i-Weight_{i+1}<=Strength_i$

那么$Next$中$min$的一定是$Strength_{i+1}-Weight_i$，而$Pre$中每一项都大于它，即交换前总优于交换后

反之，交换后优于交换前

移项得，

$Strength_i+Weight_i>=Strength_{i+1}+Weight_{i+1}$

时，交换前更优

所以我们按照$Strength+Weight$从大到小排序即可

然后$2^n$枚举选择哪些牛，对于每种情况，求出$Rest$的最小值，然后在其中取最大即可

上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int h,w,s;
}a[30];
int n,h;
bool c[30];
long long ans=-1;
bool cmp(const node &x,const node &y)
{
    return x.w+x.s>y.w+y.s;
}
void dfs(int x,int ch)
{
    c[x]=ch;
    if(x==n)
    {
        long long tmp=1e9,len=0;
        for(int i=1;i<=n;i++)
            if(c[i])
            {
                len+=a[i].h;
                long long sum=0;
                for(int j=i+1;j<=n;j++)
                    sum+=c[j]?a[j].w:0;
                tmp=min(tmp,a[i].s-sum);
            }
        if(len>=h)
            ans=max(ans,tmp);
        return;
    }
    dfs(x+1,1);
    dfs(x+1,0);
}
int main()
{
    scanf("%d%d",&n,&h);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].h,&a[i].w,&a[i].s);
    sort(a+1,a+n+1,cmp);
    dfs(0,0);
    
    if(ans==-1)
        printf("Mark is too tall\n");
    else
        printf("%lld\n",ans);
    return 0;
}