思路:
三分凹形函数极小值域
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=1e5+;
const int INF=0x7f7f7f7f;
vector<int>g[N],vc;
int n;
int cost(int x){
int need=x-g[].size(),ans=;
vc.clear();
for(int i=;i<N;i++){
for(int j=;j<g[i].size();j++){
if(g[i].size()-j>=x){
need--;
ans+=g[i][j];
}
else vc.pb(g[i][j]);
}
}
sort(vc.begin(),vc.end());
for(int i=;i<need;i++)ans+=vc[i];
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int a,b;
cin>>n;
for(int i=;i<n;i++)cin>>a>>b,g[a].pb(b);
for(int i=;i<N;i++)sort(g[i].begin(),g[i].end());
int l=g[].size(),r=n,m1=(l+l+r)/,m2=(l+r+r)/;
while(l<r){
if(cost(m1)>cost(m2)){
if(l==m1)break;
else l=m1;
}
else {
if(r==m2)break;
else r=m2;
}
m1=(l+l+r)/;
m2=(l+r+r)/;
//cout<<l<<' '<<r<<' '<<m1<<' '<<m2<<endl;
}
int ans=INF;
for(int i=l;i<=r;i++)ans=min(ans,cost(i));
cout<<ans<<endl;
return ;
}
Codeforces 458C - Elections的更多相关文章
-
Codeforces C. Elections(贪心枚举三分)
题目描述: C. Elections time limit per test 2 seconds memory limit per test 256 megabytes input standard ...
-
Codeforces Round #157 (Div. 1) B. Little Elephant and Elections 数位dp+搜索
题目链接: http://codeforces.com/problemset/problem/258/B B. Little Elephant and Elections time limit per ...
-
Little Elephant and Elections CodeForces - 258B
Little Elephant and Elections CodeForces - 258B 题意:给出m,在1-m中先找出一个数x,再在剩下数中找出6个不同的数y1,...,y6,使得y1到y6中 ...
-
Codeforces Round #503 (by SIS, Div. 2) C. Elections (暴力+贪心)
[题目描述] Elections are coming. You know the number of voters and the number of parties — n and m respe ...
-
Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections 优先队列
A. Bear and Elections ...
-
CodeForces - 369C - Valera and Elections
369C - Valera and Elections 思路:dfs,对于搜索到的每个节点,看他后面有没有需要修的路,如果没有,那么这个节点就是答案. 代码: #include<bits/std ...
-
CodeForces - 457C:Elections(三分)
You are running for a governor in a small city in Russia. You ran some polls and did some research, ...
-
codeforces Codeforces Round #318 div2 A. Bear and Elections 【优先队列】
A. Bear and Elections time limit per test 1 second memory limit per test 256 megabytes input standar ...
-
Codeforces Round #503 (by SIS, Div. 2) C. Elections(枚举,暴力)
原文地址 C. Elections time limit per test 2 seconds memory limit per test 256 megabytes input standard i ...
随机推荐
-
jenkins2 pipeline介绍
文章来自:http://www.ciandcd.com 文中的代码来自可以从github下载: https://github.com/ciandcd 什么是jenkins2的pipeline? ...
-
spring环境的搭建及作用和定义<;一>;
问题?spring的定义及作用.spring的环境搭建 一.spring的定义及作用 1.spring由Rod Johnson创建的一个开源框架,它是为了解决企业应用开发的复杂性而创建的.框架的主要优 ...
-
CSS计数器与动态计数呈现
代码: CSS代码: body { counter-reset: icecream; } input:checked { counter-increment: icecream; } .total:: ...
-
c语言的数组指针与指针数组
1. 数组指针:指向数组的指针是数组指针 先看下面一段代码: #include <stdio.h> int main(void) { int m[10]; printf("m = ...
-
ubuntu server 14.04.4 无线网卡没有启用,找不到wlan0端口
Ubuntu Server默认的情况下是不会启用无线网卡的,想想实际服务器上怎么可能有无线网卡呢,呵呵.所以我们需要手动来启用无线网卡,难点就在这里了. 使用ifconfig命令,发现没有wlan口, ...
-
count 数字计数(bzoj 1833)
Description 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. Input 输入文件中仅包含一行两个整数a.b,含义如上所述. Output 输出文 ...
-
ROS机器人程序设计(原书第2版)补充资料 (壹) 第一章 ROS系统入门
ROS机器人程序设计(原书第2版)补充资料 (壹) 第一章 ROS系统入门 书中,大部分出现hydro的地方,直接替换为indigo或jade或kinetic,即可在对应版本中使用. 第一章主要包括R ...
-
2018-2019-2 网络对抗技术 20165303 Exp6 信息搜集与漏洞扫描
实践内容 (1)各种搜索技巧的应用 (2)DNS IP注册信息的查询 (3)基本的扫描技术:主机发现.端口扫描.OS及服务版本探测.具体服务的查点(以自己主机为目标) (4)漏洞扫描:会扫,会看报告, ...
-
laravel清缓存,flex简单使用
关于laravel 删除视图缓存:php artisan view:clear 清除运行缓存:php artisan cache:clear 清除配置缓存:php artisan config:cle ...
-
CNN卷积核反传分析
CNN(卷积神经网络)的误差反传(error back propagation)中有一个非常关键的的步骤就是将某个卷积(Convolve)层的误差传到前一层的池化(Pool)层上,因为在CNN中是2D ...