题解 CF200E 【Tractor College】
RebelAlliance
·
·
题解
拖拉机学院
这不就是南翔
勘误：
输出格式那里应该是“一行三个数”，我翻译的时候打太快没看见
没错，译者写题解
思路
首先看题，似乎毫无头绪，但时间限制给了我们思路：
果断枚举
而 c_{3}, c_{4}, c_{5} 都是常数，考虑枚举 k
这样，我们就可以由 $c_{3}k_{3}+c_{4}k_{4}+c_{5}k_{5}=s$ 以$O(1)$复杂度算出 $k_{5}
枚举出的 k_{3}, k_{4}, k_{5} 若满足 c_{3}k_{3}+c_{4}k_{4}+c_{5}k_{5}=s，就是一组合法的解，算出其 f(k_{3}, k_{4}, k_{5}) 的值更新即可
细节
从0开始枚举结果过于复杂，我们不妨从最大值入手
题目中说 0 \leqslant k_{3} \leqslant k_{4} \leqslant k_5，且 c_{3}k_{3}+c_{4}k_{4}+c_{5}k_{5}=s ，所以 k_{4}, k_{5} 是 k_{3} 取最大值的“阻碍”
那么没有人拿4分或5分的时候 k_{3} 就能取到最大值了【滑稽】
当然，这种情况不符合题意，但我们讨论的是理论最大值，不用担心
接下来 k_{4} 的最大值做法类似，假装没有人拿5分
总结
代码难度不大，但思路有点难想，目测 提高+/省选-
总复杂度应该不会超过 O(s^2) （蒟蒻不会算……）
------------
### 代码
抄题解后果自负【滑稽】
```cpp
#include<con>
#define INF 2139062143
using namespace std;
int n,s;
int c3,c4,c5;
int min_f=INF;
int ans1,ans2,ans3;
int k;
inline int f(int k3,int k4,int k5){
return abs(c3*k3-c4*k4)+abs(c4*k4-c5*k5);
}//算f
inline int read(){
char ch=getchar();
int ans=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){
ans=ans*10+ch-'0';
ch=getchar();
}
return ans;
}//快读
int main(){
n=read();s=read();
for(int i=1;i<=n;i++){
k=read();//这个k下面还用来算k5，也是物尽其用【滑稽】
if(k==3)c3++;
else if(k==4)c4++;
else if(k==5)c5++;
}
for(int i=s/n;i>=0;i--){//从最大值开始枚举
for(int j=(s-c3*i)/(n-c3);j>=i;j--){//k4>=k3, 所以 j>=i
k=(s-c3*i-c4*j)/c5;
if(i*c3+j*c4+k*c5==s&&f(i,j,k)<min_f){//如果符合题意且可以更新
min_f=f(i,j,k);
ans1=i;
ans2=j;
ans3=k;//更新
}
}
}
if(min_f!=INF)printf("%d %d %d",ans1,ans2,ans3);
else printf("-1");//无解即根本没更新过
}
```