[Algo Beat Contest 005 B] 危机重重 题解
主要题意
有 个数，第 个数为 。我们可以对一个数进行任意次数的升级操作，使 ，代价为 。
求得到 个值相同的数所需的最小代价。
解题思路
这题考虑到 ，因此可以直接暴力做。
我们的思路是：对 进行升序排序，然后枚举每个数（应该从第 个枚举起，因为枚举前面的没有意义），只看不大于它的数（比它大的数没法变出来），即在数组 下标为 至 的范围内来找。把这些数升级为 的价值都记录下来。
然后，我们只需要取价值最小的 个数（还有一个数就是 本身），然后计它们代价和的最小值就行了。为了方便实现价值排序的功能，我们可以运用优先队列。综上所述，我们的解题方案时间复杂度约为 。
但是还有一点，就是这题的最大数据很大，必须要开 __int128 才能过。
代码部分
#include <bits/stdc++.h>
using namespace std;
int n, k;
__int128 ans = 1e30;
struct node
{
int p, w;
}a[1010];
bool cmp(node a, node b)
{
return a.p < b.p;
}
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i ++)
cin >> a[i].p;
for(int i = 1;i <= n;i ++)
cin >> a[i].w;
if(k == 1)//特判：只要一个数，价值一定为 0。
{
cout << 0 << endl;
return 0;
}
sort(a + 1, a + 1 + n, cmp);//升序排序
for(int i = k;i <= n;i ++)
{
priority_queue<long long> q;
for(int j = 1;j < i;j ++)//价值记录
q.push(-1ll * (a[i].p - a[j].p) * a[j].w);
__int128 cnt = 0;
for(int j = 1;j < k;j ++)//选价值最小的 k - 1 个。
cnt += (__int128)-q.top(), q.pop();
ans = min(ans, cnt);//记录最小值
}
string s = "";
while(ans)//__int128 的输出
s += (ans % 10 + '0'), ans /= 10;
reverse(s.begin(), s.end());
cout << s << endl;
return 0;
}
暂无评论