蒟蒻找了一些简单题做了而已，别太在意……
比赛链接
A. Only Pluses
题意
三个正整数 \(a,b,c\)，有五次操作机会。
每次操作：
- 选取 \(a,b,c\) 中任意一个数，将这个数加上一。
要求最大化 \(a\times b\times c\)。
思路
很直接的贪心题。
假设有三个正整数 \(x,y,z\)，给其中的某一个数加上一，那么其乘积就是 \((x+1)yz\) 或 \(x(y+1)z\) 或 \(xy(z+1)\)。
要使乘积最大，那么这个加一的数一定是 \(x,y,z\) 中最小的那个数。
以此类推，五次操作中，我们必须贪心地选取 \(a,b,c\) 中最小的数。
为了省时省力，我们可以用小根堆来维护。
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t,ans=1;cin>>t;
priority_queue<int,vector<int>,greater<int> >q;
while(t--){
ans=1;for(int i=1,x;i<=3;i++)cin>>x,q.push(x);
for(int i=1,t;i<=5;i++)
t=q.top(),q.pop(),t++,q.push(t);
for(int i=1;i<=3;i++)ans*=q.top(),q.pop();
cout<<ans<<endl;
}
return 0;
}
B. Angry Monk
题意
给定长度为 \(k\) 的序列 \(\{a_k\}\) 和正整数 \(n\)，保证 \(\sum a_i=n\)，每次可以进行一下两种操作：
-
选定一个 \(a_i(a_i>1)\)，将其分裂成 \(a_i-1\) 和 \(1\)。
-
选定 \(a_i\) 和 \(a_j\)，满足 \(a_i=1\)，将 \(a_i\) 和 \(a_j\) 合并为一个 \(a_j+1\)。
求将序列长度变为 \(1\) 的最小操作次数。
思路
依然是贪心。
如果两个数可以合并，当且仅当其中一个数为 \(1\)。
考虑 \(k=2\) 的情况，假设序列中两个元素为 \(p,q(p>q)\)，那么它的最小操作步数就是 \(2q-1\)，即先将 \(q\) 分裂为 \(q\) 个 \(1\)，再让这 \(q\) 个 \(1\) 与 \(p\) 合并。
以此类推，我们可以将序列先排序，把其中最小的 \(k-1\) 个元素分别分解为 \(1\)，在让它们和最大的元素合并。
这样就能做了。
但继续想想，可以想到一个公式：
\[ans=n-\max\{a_i\}-(k-1)+n-\max\{a_i\} \]代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[100001];
void solve(){
cin>>n>>k;for(int i=1;i<=k;i++)cin>>a[i];
sort(a+1,a+k+1);
cout<<n-a[k]-(k-1)+n-a[k]<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;cin>>t;while(t--)solve();
return 0;
}