题意：
如果最长长度的凳脚数量超过总凳脚数的一半，则认为这个凳子是稳定的。
现在有张凳子，有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("%d\n", 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;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
你并不一定会从此拥有更美好的人生，
