SP23847 ACMT - Acm Teams 题解

无咕_ · 2021-10-18 22:35:34 · 题解

题解索引

1. 题目大意
2. Solution
3. AC code
4. 类似题型

代码类型： C++（cpp）

是否吸氧：否

不压行代码长度：26

题目大意

题面： <传送门>

题意：给出 x,y，表示有 x 个元素 1 与 y 个元素 2。每次可以选择以下方式之一组成一个“组”

1. 花费 2 个元素 1 与 1 个元素 2

2. 花费 2 个元素 2 与 1 个元素 1

术语理解：分类讨论。

Solution

显而易见，我们可以看出以下三种情况可能为最优解：

1. 每个元素 1 都能和两个元素 2 组合

也就是说：

于是，这种情况的解为 x

2. 与情况 1 相反，每个元素 2 都能和两个元素 1 组合

也就是说：

于是，这种情况的解为 y

3. 每个元素 1 和元素 2 都能进行组队

也就是说：

那么解就是

当然，我们也许需要很多 if 语句，但是由于我太懒，于是推出下面式子：

首先我们看前两个式子：

我们设 t_1=\max(x,y),t_2=\min(x,y)，则有

则式子转化为：

再看最后一个式子与这个式子的关联：

首先

则

而，当我们能将全部元素都合成组时，我们一定是都要合成的，所以我们应该取两值的 \min （其实如果不满足 2t_2\le t_1 就可以直接选择 \frac{t_2+t_1}{3} 但是为了方便，我们直接取 \min）

则最终的式子为：

AC code

这里我用了 template 与 typename 创建了 read(快读) 和 _min(取最小值) 两个模板，好处是无视类型，而且可以一次填多个数值：

template<typename T>inline void read(T &x){//read记得加取地址符号&，不然没法得到读取值
    x=0;//这里要注意清零，因为是覆盖读入
    register int f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}template<typename T,typename ...Arr>inline void read(T &x,Arr &...arr){read(x);read(arr...);}
template<typename T>inline T _min(T a,T b){
    return a<b?a:b;
}template<typename T,typename ...Arr>inline T _min(T a,T b,Arr ...arr){
    return _min(_min(a,b),arr...);
}

此题的代码：

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
ll x,y,t;
template<typename T>inline void read(T &x){
    x=0;
    register int f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}template<typename T,typename ...Arr>inline void read(T &x,Arr &...arr){read(x);read(arr...);}
template<typename T>inline T _min(T a,T b){
    return a<b?a:b;
}template<typename T,typename ...Arr>inline T _min(T a,T b,Arr ...arr){
    return _min(_min(a,b),arr...);
}
int main(){
    read(t);
    while(t--){
        read(x,y);
        printf("%lld\n",_min(x,y,(x+y)/3));
    }
    return 0;
}

AC 记录 <传送门>

类似题型

暴力讨论还需要例子？直接选数论标签轮着做