显然是分数规划...主要是不会求分数的形式,看了题解发现自己好傻逼QAQ

  还是二分L值算出d[]降序选K个,顺便记录选择时候的p之和与w之和就可以输出分数形式了...

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=,inf=1e9;
struct poi{double sum;int pos;}d[maxn];
int n,K,ansx,ansy,x,y;
int p[maxn],w[maxn];
double mid;
void read(int &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
bool cmp(poi a,poi b){return a.sum-b.sum>1e-;}
bool check()
{
for(int i=;i<=n;i++)d[i].sum=1.0*p[i]-1.0*mid*w[i],d[i].pos=i;
sort(d+,d++n,cmp);
double sum=0.0;x=y=;
for(int i=;i<=K;i++)
{
x+=p[d[i].pos];y+=w[d[i].pos];
sum+=d[i].sum;
}
if(sum>=)return ;
return ;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
read(n);read(K);
for(int i=;i<=n;i++)read(w[i]),read(p[i]);
double l=,r=;
while(r-l>1e-)
{
mid=(l+r)/;
if(check())l=mid,ansx=x,ansy=y;
else r=mid;
}
ll d=gcd(ansx,ansy);
printf("%lld/%lld",ansx/d,ansy/d);
return ;
}

最新文章

  1. react入门(2)
  2. SECD machine简介
  3. c语言数据问题
  4. The 2015 China Collegiate Programming Contest K Game Rooms hdu 5550
  5. Tomcat遇到”Error listenerStart”或”Error filterStart”问题且无详细日志时的log配置.
  6. PostgreSQL的 initdb 源代码分析之七
  7. sql update小结
  8. 实例学习SSIS(五)--理论介绍SSIS
  9. 03 JVM的垃圾回收机制
  10. .NET Core 微服务架构 Steeltoe 使用(基于 Spring Cloud)
  11. pyspider和pyquery总结
  12. redis 的简单命令
  13. 神经网络4_BP神经网络
  14. JAVA学习笔记系列4-Eclipse版本选择
  15. selenium +chromdriver模块
  16. 安装ORACLE高可用RAC集群11g校验集群安装的可行性输出信息
  17. mysql 索引type介绍
  18. html背景图星际导航图练习
  19. struts2标签在jsp页面中构建map集合,循环显示
  20. SOLID原则 【转】

热门文章

  1. LabVIEW初篇---前言
  2. python学习笔记04 --------------基本运算符
  3. java 流 文件 IO
  4. 悲剧文本(Broken Keyboard (a.k.a. Beiju Text),UVA 11988)
  5. gitolite 丢失管理密钥/访问权限 解决办法
  6. BOM / URL编码解码 / 浏览器存储
  7. leetcode个人题解——#24 Swap Nodes in Pairs
  8. HDU 4308 Saving Princess claire_(简单BFS)
  9. css贝塞尔曲线模仿饿了么购物车小球动画
  10. OJ错误命令解释