【CF1251E】Voting(贪心)
2024-08-31 08:12:05
题意:有n个人,需要搞到全部n个人的票,搞到第i个人的票有两种方式:之前已经搞到mi个人的票,或者直接花费pi
问最小的搞到所有票的总代价
n<=2e5,1<=p[i]<=1e9,0<=m[i]<n
思路:考虑从大到小白嫖上限K
对于mi<=K的必定白嫖,对于mi>K的维护一个待定集合,设集合大小为size
当事实上已确定选的人数,即n-size>=K时方案合法
确定K之后需要减小size,即每次从size中选出pi最小的购买
因为待定集合一定是以mi为第一关键字从小到大排序的一个后缀,所以K需要懂大到小枚举
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
//typedef pair<ll,ll>P;
#define N 200010
#define M 200010
#define INF 1e9
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int dx[]={-,,,};
int dy[]={,,-,}; vector<int> c[N]; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void solve()
{
int n=read();
rep(i,,n)
{
int x=read(),y=read();
c[x].pb(y);
}
ll ans=;
priority_queue<int,VI,greater<int>> q;
per(i,n-,)
{
for(int j=;j<c[i].size();j++) q.push(c[i][j]);
while(q.size()>n-i)
{
ans+=q.top();
q.pop();
}
}
rep(i,,n-) c[i].clear();
printf("%I64d\n",ans);
} int main()
{
//freopen("1.in","r",stdin);
int cas=read();
while(cas--) solve();
return ;
}
最新文章
- 四、基于hadoop的nginx访问日志分析---top 10 request
- PopupWindow底部弹出
- mybatis 特殊符号及like的使用
- struts 异常机制
- oracl 创建用户
- Vmware 中安装Unix
- Jmeter 录制脚本
- 使用Application Loader打包上传AppStore流程
- TIANKENG’s rice shop
- Python设计模式——观察者模式
- php Debugging with Xdebug and Sublime Text 3(转)
- node.js(七) 子进程 child_process模块
- 谈论quick-cocos2d-x和cocos2d-x lua了解差异
- P176 test 6-1 UVa673
- Python学习之路-Day2-Python基础2
- 原生JS—实现图片循环切换及监测鼠标滚动切换图片
- JDBC(四)
- 【BZOJ4566】找相同字符(后缀数组)
- C#发送带附件的邮件的代码
- Centos安装配置Tomcat,并部署web应用