K. Farm Management 【CCPC2024哈尔滨站】

K. Farm Management

在这里插入图片描述

思路:

很容易想到的策略:

  1. 给每个作物都安排最短的时长 l l l,剩下的时间作为可支配时间。
  2. 选择删除收益最高的作物,然后将尽可能多的可支配时间用于这个作物。
  3. 或者选择删除收益低时间还长的作物,然后将时间解放出来给收益更高的作物。

关键在于3,发现难以判断选择哪个作物,所以可以将2、3合为一起。即选择每一种作物,然后将可支配时间按照收益从高到低分配。由于选择的这个作物没有了时间限制,所以先将该作物的时间 l l l解放出来加入到可支配时间中,然后按照 w w w降序分配时间,而当分配到这个被选择的作物时,就应该用完剩余可支配时间,因为在它后面的作物收益都不如它。

实现细节: 按照w降序排列作物,保存 ( r − l ) (r-l) (rl) w ( r − l ) w(r-l) w(rl) 的前缀和pc和pcw,然后遍历每种作物 i。如果可支配时间lt小于pc[i]时,可以二分pc找到能够分配到哪种作物。

代码:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long 
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
const int N = 100005;
struct zw{int l,r,w,c,cw;bool operator > (const zw &ohters)const {return w > ohters.w;}
}a[N];
int pc[N],pcw[N];  //r-l的前缀和 与  w(r-l)的前缀和void solve() {int n,t;cin>>n>>t;int sumt=0,lt,lans=0;for(int i=1;i<=n;i++){cin>>a[i].w>>a[i].l>>a[i].r;a[i].c=a[i].r-a[i].l;a[i].cw=a[i].c*a[i].w;sumt+=a[i].l;lans += a[i].l*a[i].w;}sort(a+1,a+n+1,greater<zw>()); //按照w降序排列作物for(int i=1;i<=n;i++){pc[i]=pc[i-1]+a[i].c;	pcw[i]=pcw[i-1]+a[i].cw;	}int ans = 0;for(int i=1;i<=n;i++){ //依次删除每种作物int temp=lans-a[i].w*a[i].l; //temp是除当前删除作物外,其他作物都工作l时的收入和lt =t-sumt+ a[i].l;  //lt是可支配的时间,尽可能多的把时间用在收益高的作物上if(pc[i-1]<=lt){   //利用前缀和temp+=pcw[i-1];lt-=pc[i-1];temp+= lt * a[i].w;  //i前面的作物时间都达到r时,剩余时间全部给i}else{int j = lower_bound(pc,pc+i,lt)-pc;	 //二分查找 可以分配到第j种作物temp+=pcw[j-1]+a[j].w*(lt-pc[j-1]); }ans = max(ans,temp);}cout<<ans<<endl;}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;while (T--) {solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/4961.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

智能 ODN 系统研究与设计

智能 ODN 系统研究与设计 摘 要&#xff1a;为了解决ODN面临的光纤错综复杂&#xff0c;故障定位低效等问题&#xff0c;引入电子标签&#xff0c;智能OTDR技术&#xff0c;提出了一种基于电子标签、光纤检测笔和智能OTDR故障监测的智能 ODN 解决方案,并重点讲述了智能ODN系统的…

Openlayers实现长度测量

概述 在 Openlayers 中,计算两点之间的距离,通常会用到ol/sphere模块。ol/sphere模块主要用于处理与球体(特别是地球球体)相关的数学和几何计算。而长度测量主要用到ol/sphere中的getDistance函数。 getDistance函数用于计算地球表面两点之间的距离,通常用于经纬度坐标。…

xftp连接中不成功 + sudo vim 修改sshd_config不成功的解决方法

我们使用sudo vim不成功&#xff0c;但是我们使用sudo su就可以 了&#xff01; root用户权利更大&#xff01; 喵的&#xff0c;终于成功了&#xff0c;一个xftp连接半天不成功。&#xff08;添加上面的内容就可以连接成功了↑&#xff09;

常用的c++特性-->day02

可调用对象 案例 #include <iostream> #include <string> #include <vector> using namespace std;using funcptr void(*)(int, string);int print(int a, double b) {cout << a << ", " << b << endl;return 0; } // …

应急车道占用检测算法的技术方案与应用

应急车道是高速公路上的生命通道&#xff0c;专门用于救护车、消防车、警车等紧急车辆通行&#xff0c;帮助应对突发状况。然而&#xff0c;一些驾驶员出于各种原因违规占用应急车道&#xff0c;阻碍救援车辆的正常通行&#xff0c;导致交通救援效率大幅下降&#xff0c;甚至加…

卡尔曼滤波算法Kalman filter algorithm

一、假如 状态向量服从高斯分布&#xff1a; 而且状态转移是线性的&#xff1a; 测量是状态的线性关系&#xff08;带噪声&#xff09; 初始状态的置信度也是正态分布 二、卡尔曼滤波的算法流程为 疑问&#xff1a;多测量融合&#xff0c;是不是用不同的传感器测量值去重复5…

java_继承

1.为啥用 继承? Pupil类 package com.hspedu.extend;// 小学生->模拟小学生考试的情况 public class Pupil {public String name;public int age;private double score;public void setScore(double score) {this.score score;}public void testing() {System.out.printl…

Redis 缓存击穿

目录 缓存击穿 什么是缓存击穿&#xff1f; 有哪些解决办法&#xff1f; 缓存穿透和缓存击穿有什么区别&#xff1f; 缓存雪崩 什么是缓存雪崩&#xff1f; 有哪些解决办法&#xff1f; 缓存预热如何实现&#xff1f; 缓存雪崩和缓存击穿有什么区别&#xff1f; 如何保…

【Redis的安装以及主从复制的搭建】配置Redis的哨兵模式

文章目录 一、安装Redis1、上传、解压、重命名2、安装GCC环境3、编译源码4、进行安装5、修改配置文件redis.conf 二、Redis主从复制搭建1、创建文件夹用来实现主从复制 三、配置Redis的哨兵模式1、创建文件夹2、修改sentinel.conf配置文件3、启动 一、安装Redis 1、上传、解压…

WPF中的转换器

单值转换器 1.创建项目后下载两个NuGet程序包 2.先定义一个转换器实现IValueConverter接口 using System; using System.Collections.Generic; using System.Globalization; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows; usin…

GEE Ui——批量查询Sentinel-2 图像无云区域的可视化应用(提供缩略图)

目录 简介 功能选项 函数 Map.clear() No arguments. Returns: ui.Map Map.onClick(callback) Arguments: Returns: String reduceRegion(reducer, geometry, scale, crs, crsTransform, bestEffort, maxPixels, tileScale) Arguments: Returns: Dictionary toLis…

汇编练习-1

1、要求 练习要求引自《汇编语言-第4版》实验10.3(P209页) -编程&#xff0c;将data段中的数据&#xff0c;以10进制的形式显示出来 data segment dw 123,12666,1,8,3,38 data ends 2、实现代码(可惜没找到csdn对8086汇编显示方式) assume cs:codedata segmentdw 16 dup(0) ;除…

xml格式转为txt格式?

数据集的标签格式为xml格式&#xff0c;转为yolo的训练格式&#xff1a; 1.创建一个格式转化的.py文件将下面代码复制&#xff1a; import os import glob import xml.etree.ElementTree as ETdef get_classes(classes_path):with open(classes_path, encodingutf-8) as f:cl…

M - Weird Ceiling 【CCPC2024哈尔滨站】

M - Weird Ceiling 思路: 注意到 f ( n , i ) f(n,i) f(n,i) 的值为 n y ( i ) \frac{n} {y(i)} y(i)n​ &#xff0c;其中 y ( i ) y(i) y(i) 为 n n n 小于等于 i i i 的最大因数。 那么先找到 n n n的所有因数&#xff0c;包括 1 1 1和它本身&#xff0c;在数组a[]中升…

机器学习与数学公式

目录 在机器学习中&#xff0c;将公式应用到算法程序上主要涉及以下几个步骤&#xff1a; 1、数学公式转换成编程逻辑&#xff1a; 2、选择合适的编程语言和工具&#xff1a; 3、使用矩阵运算和优化方法&#xff1a; 4、实现算法逻辑&#xff1a; 5、将公式封装成函数…

基于微信小程序的校园失物招领系统的研究与实现(V4.0)

博主介绍&#xff1a;✌stormjun、8年大厂程序员经历。全网粉丝15w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&…

芯突破 | 国产PCIe桥接芯片掀起的连接革命

PCIe桥接芯片应运而生 随着计算机技术的快速发展&#xff0c;硬件性能不断提升&#xff0c;数据传输速度的需求日益增长&#xff0c;PCIe总线凭借其高带宽和低延迟的优势&#xff0c;已经成为主流。然而&#xff0c;由于不同设备和PCIe总线之间的接口差异&#xff0c;直接连接…

6款高效网页界面原型设计软件:提升设计效率的利器

在网页设计领域&#xff0c;原型设计是将创意转化为实际产品的关键环节。一款优秀的网页界面原型设计软件能够帮助设计师快速、准确地呈现设计思路&#xff0c;优化用户体验&#xff0c;并提高团队协作效率。以下是6款在网页界面原型设计方面表现出色的软件。 1. 即时设计 即…

计算机网络综合题

IP数据报的划分 CRC差错检测 冗余码的计算 因此&#xff0c;余数是1110&#xff0c;传输的数为11010110111110。在传输过程中最后两位变成o&#xff0c;接收端能够发现&#xff0c;因为11010110111110除以10011余数不为0。 子网划分 暴力求解法 &#xff08;定长子网划分大量…

对比JavaScript、C、Python在声明变量后未初始化处理上的差异与深度解析

文章目录 &#x1f4af;前言&#x1f4af;三者声明变量后未初始化的不同默认行为JavaScriptC语言Python &#x1f4af;JavaScript中的变量管理作用域与变量声明Hoisting&#xff08;变量提升&#xff09;var的思考与缺陷 &#x1f4af;C语言中的变量管理内存模型概述变量的作用…