Codeforces 557C Arthur and Table 乱搞题

题意：

如果最长长度的凳脚数量超过总凳脚数的一半，则认为这个凳子是稳定的。

现在有张凳子，有n个凳脚，分别分出长度和砍掉该凳脚的费用。

问你要使得凳子稳定的最小费用。

思路：

其实是很简单的一题。要砍当然是砍费用小的，当时没想到怎么维护前面最小费用，然后就gg了。

首先根据长度排个序，然后枚举每种长度作为最长长度。枚举到当前长度时，相同长度不砍，把比当前长度大的全砍掉（这个比较容易维护），然后再看现在是否已经满足条件，不满足则从前面费用小的开始砍，直到满足为止。

由于费用最大值只有200，因此开个数组记录前面的情况，费用为i的个数为cnt[i]个。

code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
typedef long long LL;
int n;
int cnt[N], tsum;
struct PP {
int l, d;
bool operator < (const PP &cmp) const {
return l < cmp.l;
}
}a[N];
void solve() {
sort(a, a+n);
int res = INF;
int sum = 0;
for(int i = n-1;i >= 0; i--) {
int l = i, r = i;
cnt[a[i].d]--;
while(i != 0 && a[i].l == a[i-1].l) {
i--;
cnt[a[i].d]--;
l = i;
}
int num = r-l+1;
if(num > (r+1)/2)
res = min(res, sum);
else if(num == 1)
res = min(res, tsum-a[r].d);
else {
int kan = (r+1)-(2*num-1);
int tmp = 0;
for(int j = 1;j <= 200 && kan > 0; j++) {
if(cnt[j] != 0) {
int t = min(kan, cnt[j]);
kan -= t;
tmp += t*j;
}
}
res = min(res, sum + tmp);
}
for(int j = l;j <= r; j++) sum += a[j].d;
}
printf("%dn", res);
}
int main() {
scanf("%d", &n);
for(int i = 0;i < n; i++) scanf("%d", &a[i].l);
for(int i = 0;i < n; i++){
scanf("%d", &a[i].d);
tsum += a[i].d;
cnt[a[i].d]++;
}
solve();
return 0;
}

最后

以上就是高大蓝天为你收集整理的Codeforces 557C Arthur and Table 乱搞题的全部内容，希望文章能够帮你解决Codeforces 557C Arthur and Table 乱搞题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。