Codeforces Round #311 (Div. 2) C. Arthur and Table_outputstandard output arthur has bought a beautifu-程序员宅基地

技术标签： 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 l_i.

Arthur decided to make the table stable and remove some legs. For each of them Arthur determined numberd_i — 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.

Input

The first line of the input contains integer n (1 ≤ n ≤ 10⁵) — the initial number of legs in the table Arthur bought.

The second line of the input contains a sequence of n integersl_i (1 ≤ l_i ≤ 10⁵), wherel_i is equal to the length of thei-th leg of the table.

The third line of the input contains a sequence of n integersd_i (1 ≤ d_i ≤ 200), whered_i is the number of energy units that Arthur spends on removing thei-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

Input

3
2 4 4
1 1 1

Output

Input

6
2 2 1 1 3 3
4 3 5 5 2 1

Output
8

题意：给你一张桌子，有n条腿，告诉每条腿的长度（l）以及砍掉这条腿的花费（d），当最长腿的数量超过总数量的1/2，那么合法。问如何使得花费最小达到合法情况。
分析：暴力枚举。假设以腿长为a作为最长腿且腿a共有y条，计算花费cost需分两步：
（1）、腿长大于a的，都要砍掉，则cost+=bigger[a]；（bigger[a]可预处理得到）
（2）、腿长小于a的，假设有x条，则需要从小到大依次减去x-y+1条。由于花费d的范围只有1~200，所以可以利用花费来计算。
题目链接： http://codeforces.com/contest/557/problem/C
代码清单：

#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;
}

本文链接：https://blog.csdn.net/jhgkjhg_ugtdk77/article/details/47057619

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

简单密码---python_python简单密码加密1用8表示,2用7表示-程序员宅基地

文章浏览阅读863次。描述现在有一种密码变换算法。九键手机键盘上的数字与字母的对应：1--1，abc--2,def--3,ghi--4,jkl--5,mno--6,pqrs--7,tuv--8wxyz--9,0--0，把密码中出现的小写字母都变成九键键盘对应的数字，如：a 变成 2，x 变成 9.而密码中出现的大写字母则变成小写之后往后移一位，如：X ，先变成小写，再往后移一位，变成了 y ，例外：Z 往后移是 a 。数字和其它的符号都不做变换。数据范围：输入的字符串长度满足 1≤n≤1..._python简单密码加密1用8表示,2用7表示

AtomicMarkableReference源码解析-程序员宅基地

文章浏览阅读158次。之前在说CAS的时候说过ABA问题，ABA问题就是在多线程情况下，其他线程修改了共享变量，但最终共享变量的值并没有发生变化。以至于当前线程无法辨别共享变量是否已经发生了变化。为了使得线程..._atomicmarkablereference 源码分析

%-3d在C语言中的含义是什么？_c语言%-3d什么意思-程序员宅基地

文章浏览阅读3.1w次，点赞23次，收藏43次。定于输出格式。d表示输出整数，3表示输出的数字占3个字符的位置。-号表示对齐方式。是左对齐。如果是+号或者不写，表示右对齐。后续会继续补充。_c语言%-3d什么意思

使用vs2019编译QCAD_qcad编译-程序员宅基地

文章浏览阅读1.7k次，点赞2次，收藏12次。QCAD是一个开源的2维CAD项目。并且拥有Windows macOS以及linux跨平台的解决方案。该软件的通用交换格式是*.dxf文件，专业版的qcad也支持dwg格式文件。下面通过这篇博客详细记录一下visual studio2019+qt5.15.2编译QCAD的过程，以及编译过程中遇到的一些麻烦和解决方案：1.获取qcad源码QCAD的源码可以通过Git获取：链接如下：https://github.com/qcad/qcad ，下载qcad-master即可。完成下载后解压。2._qcad编译

shell学习笔记（3）grep -v grep|awk ‘{print $2}‘ ` 表示是什么意思_grep -v grep | awk-程序员宅基地

文章浏览阅读2.1w次，点赞16次，收藏57次。网上查阅shell定时脚本相关代码其中有一句grep -v grep|awk 'awk {print $2}'不是很理解(基础知识太薄弱)pid=`ps -ef|grep run.jar|grep -v grep|awk '{print $2}' `经查阅资料grep -v 意为不包括；上述语句的意思是查找除了grep下的所有信息,如下图所示；awk '{print $2..._grep -v grep | awk

JVM源码分析之堆外内存完全解读_jvn源码分析线程工作内存-程序员宅基地

文章浏览阅读223次。个人博客导航页（点击右侧链接即可打开个人博客）：大牛带你入门技术栈概述广义的堆外内存说到堆外内存，那大家肯定想到堆内内存，这也是我们大家接触最多的，我们在jvm参数里通常设置-Xmx来指定我们的堆的最大值，不过这还不是我们理解的Java堆，-Xmx的值是新生代和老生代的和的最大值，我们在jvm参数里通常还会加一个参数-XX:MaxPermSize来指定持久代的最大值，那么我们认识..._jvn源码分析线程工作内存

随便推点

[实战] 朴素贝叶斯分类器进行垃圾邮件过滤_朴素贝叶斯分类器和svm在垃圾邮件过滤任务中-程序员宅基地

文章浏览阅读1.7k次。我们已经讲解过朴素贝叶斯分类器的基本原理和实现：动手实现朴素贝叶斯分类器进行文档分类在此基础上，我们实现垃圾邮件的过滤，数据为50封txt邮件（1）将text文本文件，分成单词列表使用正则表达式，使用除单词和数字外的任意字符串为分隔符并删除长度小于3的字符串def textParse(bigString): import re listOfTokens = re.spli..._朴素贝叶斯分类器和svm在垃圾邮件过滤任务中

cvs 常用命令记录-程序员宅基地

文章浏览阅读130次。//z 纯粹自己备忘//z 9/19/2011 1:22 [email protected] 命令的形式：cvscvs-options subcommand subcommand-options查看帮助：cvs-H subcommandcvs status -h检出文件：cvscheckout mymodule更新cvs..._cvs 回滚

AudioTrack 播放wav音频文件_audioformat.encoding.pcm_float不生效-程序员宅基地

文章浏览阅读595次。我们要想对wav文件格式操作，我们就要了解wav的文件格式https://blog.csdn.net/qq_15255121/article/details/115168456通过上面我们可以知道第8到11字节代表当前是wave格式也就是wav格式第20-21字节代表当前的音频数据是什么格式如果是1代表是pcm格式第24-28字节，代表当前的采样率第34-35字节，代表当前的采样大小（位深）第44字节开始，是我们真是的数据通过上面的分析我们可以知道，wav只是把p._audioformat.encoding.pcm_float不生效