自动搬运

查看原文

来自洛谷，原作者为

	GeorgeDeng 不拿7钩不改签 || 估值不上300不改签 || ccf太坑人了！！！ || 最后在线时间: 2025/8/24 21:35

搬运于2025-08-24 23:13:07，当前版本为作者最后更新于2025-04-12 21:15:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

$T$ 组数据，每组数据有 $a$ 个糖果和 $b$ 个曲奇。有两种删除操作：

• 选出 $2$ 个糖果或者 $2$ 个曲奇，代价为 $x$；
• 选出 $1$ 个糖果和 $1$ 个曲奇，代价为 $y$。

求删完糖果或曲奇的最小代价。

思路

一道分类讨论题。

因为有可能 $x>2y$，所以如果出现这种情况的时候，一个一个删除更优，可以直接把 $x$ 赋值为 $2\times y$。

接下来就是计算。我们讨论把糖果删完和把曲奇删完的代价，答案就是删完糖果的代价与删完曲奇的代价中取最小值。糖果或曲奇删除的代价怎么算？因为两个两个删效果更快，而且不用考虑另外一个东西，所以优先两个两个删，代价为数量除以 $2$ 再乘上 $x$。然后把不足以两个两个删的一个一个删就行了，代价是数量对 $2$ 取模再乘上 $y$。综上可以推出式子 $ans=\min(a\div 2 \times x+a \bmod 2 \times y,b\div 2 \times x+b \bmod 2 \times y)$。

注意并不是哪个少优先删哪个，我就是因为这个被卡了 $30min$。

code:

#include <iostream>
#define int long long
using namespace std;

signed main()
{
    int t;
    cin>>t;
    while(t--){
        int a,b,x,y;
        cin>>a>>b>>x>>y;
        if(x>2*y) x = 2*y;//如果两个一起删除还没有一个一个删除代价低，就x=2*y
        cout<<(min(((a/2)*x+(a%2)*y),(b/2)*x+(b%2)*y))<<endl;//直接求答案
    }
    return 0;
}