CodeForces 492C Vanya and Exams (贪心)
1 second
256 megabytes
standard input
standard output
Vanya wants to pass n exams and get the academic scholarship. He will get the scholarship if the average grade mark for all the exams is at least avg. The exam grade cannot exceed r. Vanya has passed the exams and got grade ai for the i-th exam. To increase the grade for the i-th exam by 1 point, Vanya must write bi essays. He can raise the exam grade multiple times.
What is the minimum number of essays that Vanya needs to write to get scholarship?
The first line contains three integers n, r, avg (1 ≤ n ≤ 105, 1 ≤ r ≤ 109, 1 ≤ avg ≤ min(r, 106)) — the number of exams, the maximum grade and the required grade point average, respectively.
Each of the following n lines contains space-separated integers ai and bi (1 ≤ ai ≤ r, 1 ≤ bi ≤ 106).
In the first line print the minimum number of essays.
5 5 4
5 2
4 7
3 1
3 2
2 5
4
2 5 4
5 2
5 2
0 思路: 平均分其实乘一下n以后就是总分,也就是说总分要达到这个sum=avg*n,而每一科提升一分的代价是bi个论文,提升空间则还有r-ai个学分。计算好每个科目以后,贪心取代价最小的,按bi从小到大排序,能取多少就取多少,直到分数达到sum为止,性价比最高的科目的提分空间用完以后再去性价比第二高的科目。
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF = 1e9;
const double eps = 1e-;
//const int N = ;
int cas = ; ll n,r,avg,sum; void run()
{
ll a,b;
vector<pii> v;
sum = avg * n;
for(int i = ; i < n; i++ )
{
cin >> a >> b;
sum -= a;
v.push_back(make_pair(b,r-a));
}
sort(v.begin(),v.end());
ll ans = ;
for(int i = ; i < n; i++ )
{
if(sum <= ) break;
if(sum >= v[i].second)
ans+=v[i].first*v[i].second, sum-=v[i].second;
else
ans += sum*v[i].first, sum -= sum;
}
cout << ans << endl;
} int main()
{
#ifdef LOCAL
// freopen("case.txt","r",stdin);
#endif
while(cin >> n >> r >> avg)
run();
return ;
}
最新文章
- 转载:CSS3 Flexbox可视化指南
- Scrum会议10.20
- php大力力 [014节] 八杆子打不着的非技术文章,哈哈
- 【转】eclipse 安装插件
- Python尾递归-求斐波那契数列
- java开发webservice的几种方式
- HDU 5805 NanoApe Loves Sequence
- Python实战之文件操作的详细简单练习
- 卸载CentOS7-x64自带的OpenJDK并安装Sun的JDK7的方法
- Jupyter Notebook 快速入门
- Cocos2D iOS之旅:如何写一个敲地鼠游戏(八):为动画建立属性列表
- 浅析 jQuery 内部架构设计
- ubuntu html5开发工具brackets
- java日志
- [UE4]打包EXE
- python-html-百度云音视频点播服务
- Could not update Activiti database schema: unknown version from database: &#39;5.20.0.1&#39;
- MongoDB学习笔记(二)
- Maven学习(十八)-----Maven依赖管理
- python-爬虫技能升级记录
热门文章
- [原创]java WEB学习笔记31:会话与状态管理 session机制 概述(定义,session机制,session的声明周期,保存session的方式,Session的创建与删除)
- mysql 历史数据表迁移方案
- 斯坦福机器学习视频笔记 Week2 多元线性回归 Linear Regression with Multiple Variables
- RabbitMQ之Exchange
- Java -- AWT 画图,图像处理
- Sqoop- sqoop将mysql数据表导入到hive报错
- Jquery实现超酷的时间轴特效
- 从request中读数据流
- Sharepoint list webpart
- Saiku_学习_03_Saiku+Kylin构建多维分析OLAP平台