【35.29%】【codeforces 557C】Arthur and Table
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard 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.
Examples
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
【题目链接】:http://codeforces.com/contest/557/problem/C
【题解】
可以从最后的答案出发;
先枚举最大的数是多少;
假设它出现的次数为x;
则为了使得他出现的次数大于总的桌腿个数/2;
则最多还需要增加x-1条桌腿才行;
显然要使得x-1条桌腿耗费的总能量最大;
(因为要消耗的能量是砍掉所有桌腿的能量总和减去这2*x-1条桌腿的能量);
这样消耗的能量最小;
同时,比这个桌腿长的桌腿不能出现,所以只能在比这个桌腿短的桌腿中找x-1条桌腿(总和最大);
具体实现:
用计数排序搞;
一开始按照桌腿长度升序排;
然后顺序枚举桌腿i;
rep1(i,1,n)
{
int l = i,r = i+1,temp=a[i].d;//temp是这2*x-1条桌腿的总能量
while (a[r].l==a[l].l)//是同一种桌腿就累加
{
temp+=a[r].d;
r++;
}
int x = r-l-1;//还要找x-1条桌腿;
//printf("%d\n",x);
rep2(j,200,1)//因为桌腿的能量最大为200所以可以用计数排序,这样满足优先找能量最大的桌腿,且桌腿的长度比该桌腿短.
{
if (x==0) break;//桌腿的数目够了就结束
int s = min(x,bo[j]);
temp+=j*s;//s是这个桌腿的数量,j是它的能量;
x-=s;
}
temp1 = max(temp1,temp);
rep1(j,l,r-1)//搞个前缀和
bo[a[j].d]++;
i = r-1;
}
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
#define pri(x) printf("%d",x)
#define prl(x) printf("%I64d",x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 1e5+10;
const int MNUM = 200+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
struct abc
{
int l,d;
};
int n,sum=0;
abc a[MAXN];
int bo[MNUM];
bool cmp(abc a,abc b)
{
return a.l < b.l;
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
rei(n);
rep1(i,1,n)
rei(a[i].l);
rep1(i,1,n)
rei(a[i].d),sum+=a[i].d;
sort(a+1,a+1+n,cmp);
int temp1 = 0;
rep1(i,1,n)
{
int l = i,r = i+1,temp=a[i].d;
while (a[r].l==a[l].l)
{
temp+=a[r].d;
r++;
}
int x = r-l-1;
//printf("%d\n",x);
rep2(j,200,1)
{
if (x==0) break;
int s = min(x,bo[j]);
temp+=j*s;
x-=s;
}
temp1 = max(temp1,temp);
rep1(j,l,r-1)
bo[a[j].d]++;
i = r-1;
}
printf("%d\n",sum-temp1);
return 0;
}
相关文章
- 解决Please make sure you have the correct access rights and the repository exists 问题.
- PI Week5 Bias and Fairness 施工中~
- ORA-19728: data object number conflict between table string and partition string in table string ORACLE 报错 故障修复 远程处理
- ORA-23370: table string and table string are not shape equivalent (string) ORACLE 报错 故障修复 远程处理
- ORA-24072: cannot execute MIGRATE_QUEUE_TABLE procedure; must own queue table ORACLE 报错 故障修复 远程处理
- ORA-31498: description and remove_description cannot both be specified ORACLE 报错 故障修复 远程处理
- ORA-31679: Table data object string has long columns, and longs can not be loaded/unloaded using a network link ORACLE 报错 故障修复 远程处理
- ORA-39148: unable to import data into pre-existing queue table string. Table_exists_action of string being ignored for this table ORACLE 报错 故障修复 远程处理
- ORA-39360: Table string was skipped due to transportable import and TSLTZ issues resulting from time zone mismatch. ORACLE 报错 故障修复 远程处理
- ORA-55316: model string does not match model string for table and column ORACLE 报错 故障修复 远程处理
- ORA-02464: Cluster definition can not be both HASH and INDEX ORACLE 报错 故障修复 远程处理
- ORA-13904: The file has been dropped and recreated during the procedure call. ORACLE 报错 故障修复 远程处理
- ORA-14095: ALTER TABLE EXCHANGE requires a non-partitioned, non-clustered table ORACLE 报错 故障修复 远程处理
- ORA-14296: Table block size mismatch in ALTER TABLE EXCHANGE [SUB]PARTITION ORACLE 报错 故障修复 远程处理
- ORA-14757: Table is already a range partitioned table ORACLE 报错 故障修复 远程处理
- ORA-16445: Database has to be mounted and cannot be open ORACLE 报错 故障修复 远程处理
- Apache PHP and MySQL: A Match Made in Heaven(apachephpmysql)
- 多条件查询MySQL中使用And多条件查询的步骤(mysql中and)
- Linux TGZ: All You Need to Know About Tar and Gzip Compression!(linuxtgz)
- Exploring the Power and Versatility of SAR on the Linux Platform(sarlinux)
- Building Complex Database Applications Made Easy with Linux QT and SQL(linuxqtsql)
- Introduction to Linux LVM and How to Extend LVM with the PE Concept(linuxlvmpe)
- MySQL中的AND逻辑操作符是什么(mysql中and是什么)