正解:01分数规划

解题报告:

板子题鸭,,,

显然考虑变成$a[i]-mid\cdot b[i]$,显然无脑贪心下得选出最大的$k$个然后判断是否大于0就好(,,,这么弱智真的算贪心嘛$TT$

然后就做完辣,,,

我真的$jio$得我做的题越来越水了是为什么,,,啊难过,越来越菜了可海星$TT$

#include<algorithm>

#include<iomanip>

#include<cstdio>

using namespace std;

#define il inline

#define lf double

#define gc getchar()

#define rf register lf

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

const int N=+;const lf eps=1e-;

int n,K;

bool gdgs=;

struct node{lf a,b,dat;}nod[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(node gd,node gs){return gd.dat<gs.dat;}

il bool chck(rf x)

{

    lf sum=;rp(i,,n)nod[i].dat=(lf)nod[i].a*-nod[i].b*x,sum+=nod[i].dat;sort(nod+,nod++n,cmp);

    rp(i,,K)sum-=nod[i].dat;return sum>=;

}

int main()

{

    while(gdgs)

    {

        n=read();K=read();if(!n && !K)return ;

        rp(i,,n)scanf("%lf",&nod[i].a);rp(i,,n)scanf("%lf",&nod[i].b);

        rf l=,r=;

        while(r-l>eps){rf mid=(lf)(l+r)/;if(chck(mid))l=mid;else r=mid;}

        printf("%.0f\n",l);

    }

    return ;

}

啊对了说一个这题杀我的点,,,就是$double$的输出要用$lf$,,,具体原因看评论区趴懒得贴过来了$QwQ$,,,$get$了一个新知识点呢$QwQ$

随机推荐

[Machine-Learning] matlab 矩阵常见基本操作
概述对矩阵的主要操作,matlab 中都有现成的指令或者库函数与之对应. 矩阵最早来自于方程组的系数和常数所构成的方阵,这一概念是由19世纪的英国数学家凯利提出的. 创建矩阵这里写的不全,但是足够 ...
Oracle Essbase入门系列（一）
1. 开篇序本文是几年前做Hyperion Planning项目时写的,后来陆陆续续有些补充.本来打算将整个EPM写一系列的教程,但HFM写到1/3就没动力了.不过至少Essbase这部分是完整的. ...
R语言简单聚类分析
#以R基础包自带的鸢尾花(Iris)数据进行聚类分析iris data <- iris[,:] #系统聚类法(层次聚类法) distance <- dist(data) #计算距离 iri ...
java&lowbar;常用数据类型转换基础篇
一.java基本数据类型 1.java基本数据类型可分四类八中第一类:整形:byte.short.int.long 第二类:浮点型:float(单精度) .double(双精度) 第三类:逻辑类型: ...
剑指offer-面试题15&period;链表中倒数第k个结点
题目:输入一个链表,输出该链表的倒数第K个结点.为了符合大多数人的习惯,本题从1开始计数,即链表的尾结点是倒数第1个节点.例如有一个链表有6个节点,从头节点开始他们的值依次是1,2,3,4,5,6 ...
ThinkPHP框架的增删改
使用TP框架主要是比较简单一些,之前我们写增删改,代码量相对来说还是比较多的,这里利用tp框架写起来是非常简单的,大大的减少了代码量这里我是以数据库的nation表为例的,nation表 ...
使用nvm管理node不同版本，安装，环境配置，切换不同版本的node版本
文章包含以下内容: 一.下载地址二.nvm-noinstall.zip安装三.nvm-setup.zip安装四.测试安装以及使用一.下载地址 https://github.com/coreyb ...
&period;NET&colon; 使用&period;NET Core CLI开发应用程序
要开发.NET Core应用程序,除了使用强大的Visual Studio之外,还可以使用.NET Core CLI..NET Core CLI (Command-Line Interface),也就 ...
RabbitMQ广播：topic模式
topic模式跟direct差不多,只是把type改一下就行. direct是把固定的routing_key跟queue绑定,topic是把模糊的routing_key跟queue绑定原理图: 发布 ...
我的vim插件配置
set nocompatible " be iMproved, required filetype off " required " set the runtime pa ...

秒客网

$POJ$2976 $Dropping\ tests$ 01分数规划+贪心

正解:01分数规划

解题报告:

随机推荐

相关文章