技术标签： brute force 思维技巧 codeforces 贪心 greedy acm algorithm
Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.
In total the table Arthur bought has n legs, the length of thei-th leg is li.
Arthur decided to make the table stable and remove some legs. For each of them Arthur determined numberdi — the amount of energy that he spends to remove thei-th leg.
A table with k legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with5 legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.
Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.
The first line of the input contains integer n (1 ≤ n ≤ 105) — the initial number of legs in the table Arthur bought.
The second line of the input contains a sequence of n integersli (1 ≤ li ≤ 105), whereli is equal to the length of thei-th leg of the table.
The third line of the input contains a sequence of n integersdi (1 ≤ di ≤ 200), wheredi is the number of energy units that Arthur spends on removing thei-th leg off the table.
Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.
2 1 5 3 2
2
3 2 4 4 1 1 1
0
6 2 2 1 1 3 3 4 3 5 5 2 1
#include<queue>
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const ll maxv = 1e10 + 5;
int n;
struct Edge{int l,d;}leg[maxn];
int cost[maxn];
ll Back[maxn];
int num[maxn];
bool cmp(Edge a,Edge b){
return a.l<b.l;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&leg[i].l);
num[leg[i].l]++;
}
for(int i=0;i<n;i++)
scanf("%d",&leg[i].d);
sort(leg,leg+n,cmp);
ll sum=0;
for(int i=n-1;i>0;i--){ //计算腿长比leg[i-1].l大的总花费
sum+=(ll)leg[i].d;
if(leg[i].l!=leg[i-1].l){
Back[leg[i-1].l]=sum;
}
}
ll ans=Back[leg[0].l];
cost[leg[0].d]++;
for(int i=1;i<n;i++){
if(leg[i].l!=leg[i-1].l){
int an=i-num[leg[i].l]+1;
sum=Back[leg[i].l];
if(an>0){
for(int j=1;j<=200;j++){ //从小到大依次减去an数量的腿
if(cost[j]){
if(cost[j]>=an){
sum+=(an*j);
an=0;
break;
}
else{
sum+=(cost[j]*j);
an-=cost[j];
}
}
}
}
ans=min(ans,sum);
}
cost[leg[i].d]++;
}
printf("%I64d\n",ans);
return 0;
}
文章浏览阅读358次。1.介绍图的相关概念 图是由顶点的有穷非空集和一个描述顶点之间关系-边（或者弧）的集合组成。通常，图中的数据元素被称为顶点，顶点间的关系用边表示，图通常用字母G表示，图的顶点通常用字母V表示，所以图可以定义为: G=(V,E)其中，V(G)是图中顶点的有穷非空集合，E(G)是V(G)中顶点的边的有穷集合1.1 无向图：图中任意两个顶点构成的边是没有方向的1.2 有向图：图中..._给定一个邻接矩阵未必能够造出一个图
文章浏览阅读1.7k次。问题:IAR调试STM32程序，点击调试按钮后软件自动关闭，并弹出报错提示框解决：将调试的接口模式改为SWD模式即可。我的原先设置为JTAG模式。_iar在debug时停止工作
文章浏览阅读742次。100兆宽带的网速通常指的是每秒可以传输的数据量为100兆比特（Mb）。在此情况下，1兆比特（Mb）等于100万比特（Mbps），而1字节（B）等于8比特（bps）。因此，100兆宽带的网速可以计算如下：100兆比特/秒=100/8 兆字节/秒= 12.5兆字节/秒所以，100兆宽带的网速约为12.5MBps（兆字节/秒），也可以说为100Mbps（兆比特/秒）。但是需要注意的是，实际的下载和上传速度可能受到各种因素的影响，如网络拥堵、设备性能等。因此，实际使用中您可能会感受到较低的速度。_100m的宽带网速是多少兆
文章浏览阅读2.4w次，点赞13次，收藏44次。Windows 7 通用 CDC 串口驱动程序Windows 7 自带 CDC 串口类设备的驱动程序文件 usbser.sys，所缺的是驱动配置文件 usbser.inf 文件，将 Windows 10 的 usbser.inf 文件拷贝到 Windows 7，注释掉 SourceDisksNames 和 SourceDisksFiles 部分就可以作为 Windows 7 的 CDC 串口类..._cdcserial驱动 win7
文章浏览阅读2.5k次，点赞53次，收藏51次。NLP-词表示_nlp中词语的表示
文章浏览阅读2.4k次。sed -i 's/[ ][ ]*/ /g' file.txt _sed 多个空格替换为1个
文章浏览阅读1.7w次，点赞15次，收藏129次。算法（algorithm）是解决一系列问题的清晰指令，也就是，能对一定规范的输入，在有限的时间内获得所要求的输出。 简单来说，算法就是解决一个问题的具体方法和步骤。算法是程序的灵 魂。二、算法的特征1.可行性 算法中执行的任何计算步骤都可以分解为基本可执行的操作步，即每个计算步都可以在有限时间里完成（也称之为有效性） 算法的每一步都要有确切的意义，不能有二义性。例如“增加x的值”，并没有说增加多少，计算机就无法执行明确的运算。 _算法
文章浏览阅读1.5k次，点赞18次，收藏26次。网络安全的标准和规范是网络安全领域的重要组成部分。它们为网络安全提供了技术依据，规定了网络安全的技术要求和操作方式，帮助我们构建安全的网络环境。下面，我们将详细介绍一些主要的网络安全标准和规范，以及它们在实际操作中的应用。_网络安全标准规范
文章浏览阅读1.5k次。Chocolatey是什么？很简单，Chocolatey就是Windows系统的yum或apt-get。一、Chocolatey介绍Chocolatey是一款专为Windows系统开发的、基于NuGet的包管理器工具，类似于Node.js的npm，MacOS的brew，Ubuntu的apt-get，它简称为choco。Chocolatey的设计目标是成为一个去中心化的框架，便于开发_chocolate怎么卸载
文章浏览阅读2.3w次，点赞177次，收藏741次。Python作为21世纪最火的编程语言，市面上各种学习视频层出不穷，关于Python的学习氛围也逐渐浓厚，Python固然简单好上手，但事实上Python也不是那么容易学习的。如果不采取正确的学习方式，很容易走入误区。关于Python的三个谎言，你一定要清楚。1： 学完Python，并不能立马拿一两万的工资，甚至可能找不到工作！2：Python也没有那么简单，不是有手就行！3：别想着1个星期、2个星期就能学会，你至少得腾出一两个月来连续学习！如果你还是执意要学Python，那么好，接下来我们看看怎._关于python 盲目
文章浏览阅读2.1k次。方法一将table标签，包括tr、td等对json数据进行拼接，将table输出到表格上实现，这种方法的弊端在于输出的是伪excel，虽说生成xls为后缀的文件，但文件形式上还是html，代码如下<html><head> <p style="font-size: 20px;color: red;">使用table标签方式将json导出xls文件</p..._如何把js数据转换成表格
IEEE协会是一个专注于航空与电子系统领域的组织，注册IEEE会员可以享受许多权益，包括免费访问协会资源中心和参加各种会议及活动。