Codeforces Round #311 (Div. 2) C. Arthur and Table (枚举+贪心+思维)_weixin_34221112的博客-程序员宅基地

C. Arthur and Table
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 the i-th leg is li.

Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number di — the amount of energy that he spends to remove the i-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 with 5 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.

Input

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 integers li (1 ≤ li ≤ 105), where li is equal to the length of the i-th leg of the table.

The third line of the input contains a sequence of n integers di (1 ≤ di ≤ 200), where di is the number of energy units that Arthur spends on removing the i-th leg off the table.

Output

Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.

Sample test(s)
Input
2
1 5
3 2
Output
2
Input
3
2 4 4
1 1 1
Output
0
Input
6
2 2 1 1 3 3
4 3 5 5 2 1
Output
8

题意:
一张桌子有n条长度不全相同的腿,拆掉每个桌腿有一定代价。
长度为最大值的桌腿数量必须超过此时桌腿总量的一半,桌子才算平稳。
问要想使桌子平衡最少需要付出多少代价。

分析:
枚举稳定时桌腿长度的最大值L,那么超过L的桌腿一定要拆掉。
如果拆掉了比L长的桌腿仍不满足L长度的桌腿超过总桌腿的一半,则从比L小的桌腿中拆除代价小的桌腿。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define eps 10e-13

using namespace std;

typedef long long ll;

struct node
{
    int l,d;
}leg[100010];
int num[100010];     //num[i]:长度为i的桌腿数量
int c[100010];  //c[i]:排序后前i+1条桌腿的拆除总代价
int n[100010];  // n[i]:长度小于等于i的桌腿的总数量
int D[205];     // D[i]:拆除代价为i的桌腿数量

bool cmp(node x,node y)  //按桌腿长度从小到大,长度相等时拆除代价从小到大排序
{
    if(x.l == y.l) return x.d<y.d;
    return x.l<y.l;
}

int main()
{
    int N;
    while(~scanf("%d",&N))
    {
        memset(c,0,sizeof(c));
        memset(num,0,sizeof(num));
        memset(n,0,sizeof(n));
        memset(D,0,sizeof(D));

        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);
        c[0] = leg[0].d;
        for(int i=1;i<N;i++)
            c[i] = c[i-1]+leg[i].d;
        n[0] = 0;
        for(int i=1;i<=100000;i++)
            n[i] = n[i-1]+num[i];

        int res = 0x3f3f3f3f;
        for(int i=1;i<=100000;i++)   //枚举最长桌腿长度
        {
            if(!num[i]) continue;
            int tmp = n[i]-(2*num[i]-1);   //最长桌腿长度为i时,长度为i的桌腿数量是否大于总量一半
            int cur = c[N-1]-c[n[i]-1];    //cur=拆除长度>i的桌腿所花代价
            while(tmp>0)  //如果数量不过半,则从长度小于i的桌腿中选择代价小的拆除
            {
                for(int j=1;j<=200;j++)
                {
                    if(D[j]<=tmp)   //代价为j的数量D[j]
                    {
                        cur += D[j]*j;
                        tmp -= D[j];
                    }
                    else
                    {
                        cur += tmp*j;
                        tmp = 0;
                    }
                }
            }
            res = min(res,cur);   //更新答案
            for(int j=n[i-1];j<n[i];j++)   //按长度为i的桌腿的代价更新D,以便继续往后递推时
                D[leg[j].d]++;        //D[j]仍然记录的是桌腿长度小于所枚举值的代价为j的桌腿数量
        }
        printf("%d\n",res);
    }
    return 0;
}
View Code

 

转载于:https://www.cnblogs.com/hadis-yuki/p/4689442.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_34221112/article/details/94684086

智能推荐

【Spark2运算效率】第六节 影响生产集群运算效率的原因之网络IO_Jack_Roy的博客-程序员宅基地

【Spark2运算效率】第六节 影响生产集群运算效率的原因之网络IO前言问题概述案例结语跳转前言在磁盘IO速率和网络接口IO传输速率匹配的情况下,更快的网络IO能够极大提升Spark程序Shuffle过程中Executor交换数据的速度,认识到这一点,网络IO对于集群效率的影响不言而喻,主机间可用带宽越高就意味着Spark程序数据交换速度越快;问题概述在前言中,我着重强调了主机间的可用带宽越高,Spark程序数据交换速度越快,而不是机房环境的整体网络带宽。对于整个集群的调度来说,机房带宽越高,集群整

详解高性能计算中的异构计算_架构师技术联盟的博客-程序员宅基地

当摩尔定律还是行业的铁律时,计算机编程几乎一直都是串行的,绝大多数的程序只存在一个进程或线程。大家还过着“我写个程序,性能达不到就睡个觉,等硬件工艺刷新硬件性...

idea将最普通的javaweb项目为war包部署到服务器_燃一燃的博客-程序员宅基地

idea怎么打包javaweb项目为war包并放到tomcat下启动我们javaweb项目结构如下:我们想打把这个javaweb项目打包为war包,该javaweb项目是非maven项目,因此不能通过pom文件中添加依赖的方式打war包。具体打包步骤如下:点击下图中的红框位置:打开后,如下图:依次配置好projects, moudles, libraries,Facets选项,选中Artifacts,点击“+”,选中Artifacts,点击“+”,出现如下图:继续点击“+”,依次执行如图

第36届ACM 北京区域赛邀请赛 F题_magicnumber的博客-程序员宅基地

F  F LOOPS[Description]Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl).Homura wants to help her friend Madoka save the world. But

easyexcel的源码简单分析_怒放de生命2010的博客-程序员宅基地_easyexcel源码解析

文章目录读的流程图逻辑分析1.EasyExcel2.EasyExcelFactoryExcelReaderSheetBuilderExcelReaderExcelAnalyserImplXlsxSaxAnalyserDefaultAnalysisEventProcessorDemoDatalistener的invoke()方法被调用返回到XlsxSaxAnalyserDefaultAnalysisEventProcessor的endSheet()DemoDataistener的doAfterAllAnaly

随便推点

CVPR 2019 | CVPR2019 论文接收列表_youli_3的博客-程序员宅基地

原文地址:https://blog.csdn.net/Sophia_11/article/details/886726351】Learning Regularity in Skeleton Trajectories for Anomaly Detection in Videos(Romero Morais;Vuong Le;Truyen Tran;Budhaditya Saha;M...

Delphi的常用函数_知其然所以然的博客-程序员宅基地

Delphi 的常用函数:转换函数:StrToFloat()  转换成浮点数IntToStr()  转换成字符串其它转换函数类似数学类函数:         绝对值函数  Abs(x);         去整函数        Trunc(x) : Int64;  //返回整数部分                         

java 安装失败7640,SQLException_weixin_39542340的博客-程序员宅基地

SQLExceptionSQLExceptionjava.sql.SQLException:[Microsoft][SQLServer2000DriverforJDBC]Errorestablishingsocket.为什么??代码应该没有错!:我用之前已经装了SP4搜索更多相关的解决方案:SQLException"target="_blank"&gt;color...10热度java.sql.S...

POJ--3268--Silver Cow Party【SPFA+邻接表】_altair21的博客-程序员宅基地

题意:一些牛要去某一点参加聚会,然后再回到自己家,路是单向的,问花费时间最多的那头牛最少需要花费多长时间。思路:从聚会地点返回,相当于是从某一点到其他各个点的最短路径。从牛的家中走到聚会地点,可以把路径反过来变成从聚会地点到各个点的最短路径,两个最短路径值加起来就是每头牛所花费的最小时间,找出最大的即可。我用了两个邻接表存路径,其实这道题用邻接矩阵存更好做,矩阵横纵坐标翻转就把路径

javaweb学习--导航_金刀李的博客-程序员宅基地

之前不管学习还是工作,都有接触web方面的内容,但是都是零零散散的,感觉自己学的不够系统,刚好中秋放几天假,打算系统的学习一下这方面的知识!这个算是一个导航帖吧,后面每天更新一下自己的学习进度,顺便把博客链接放到这里面来。

NodeManager代码分析之NodeManager启动过程_笃志近思的博客-程序员宅基地

1、NodeManager概述NodeManager(NM)是YARN中每个节点上的代理,它管理Hadoop集群中单个计算节点,包括与ResourceManger保持通信,监督Container的生命周期管理,监控每个Container的资源使用(内存、CPU等)情况,追踪节点健康状况,管理日志和不同应用程序用到的附属服务。2、NodeManager分析2.1、代码分析接下来将