I - Protecting the Flowers

这篇具有很好参考价值的文章主要介绍了I - Protecting the Flowers。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport each cow back to its own barn.

Each cow i is at a location that is Ti minutes (1 ≤ Ti ≤ 2,000,000) away from its own barn. Furthermore, while waiting for transport, she destroys Di (1 ≤ Di ≤ 100) flowers per minute. No matter how hard he tries, FJ can only transport one cow at a time back to her barn. Moving cow i to its barn requires 2 × Ti minutes (Ti to get there and Ti to return). FJ starts at the flower patch, transports the cow to its barn, and then walks back to the flowers, taking no extra time to get to the next cow that needs transport.

Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.

Input

Line 1: A single integer N
Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics

Output

Line 1: A single integer that is the minimum number of destroyed flowers

Sample

Inputcopy Outputcopy
6
3 1
2 5
2 3
3 2
4 1
1 6
86

Hint

FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. While he is transporting cow 6 to the barn, the others destroy 24 flowers; next he will take cow 2, losing 28 more of his beautiful flora. For the cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. When he picks cow 5 there are no more cows damaging the flowers, so the loss for that cow is zero. The total flowers lost this way is 24 + 28 + 16 + 12 + 6 = 86.

有 n 头奶牛跑到 FJ 的花园里去吃花儿了,它们分别在距离牛圈 Ti​(这里指 FJ 到那里需要 Ti​ 分钟) 处吃花,每分钟会吃掉 Di​ 朵花,FJ 现在要将它们给弄回牛圈,但是他每次只能弄一头回去,来回用时总共为 2×Ti​ 分钟,在这段时间内,其它的奶牛会继续吃 FJ 的花,速度保持不变,当然正在被赶回牛圈的奶牛不能继续吃了。现在求在最好的方案下奶牛吃掉花的最小朵数。文章来源地址https://www.toymoban.com/news/detail-704650.html

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

const int N = 1e5 + 500;
typedef long long ll;
vector<pair<ll, ll>> vv;
ll a[N];

bool cmp(pair<ll, ll> p1, pair<ll, ll> p2)
{
	return p1.first * p2.second < p2.first * p1.second;
	//送牛一回去的时间牛二吃草量小于送牛二回去牛一的吃草量
	//则优先送牛一回去,以此规律排序
}

int main()
{
	ll n, sum = 0; scanf_s("%lld", &n);
	for (ll i = 0; i < n; i++)
	{
		ll n1, n2; scanf_s("%lld%lld", &n1, &n2);
		vv.push_back(make_pair(n1, n2));
	}

	sort(vv.begin(), vv.end(), cmp);

	for (int i = 0; i < vv.size(); i++) a[i] = a[i - 1] + vv[i].second;

	for (int i = 0; i < vv.size(); i++) sum += 2 * vv[i].first * (a[vv.size() - 1] - a[i]);

	cout << sum << endl;

}

到了这里,关于I - Protecting the Flowers的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 鸿蒙app启动远程平板报错解决方法The type of the target device does not match the deviceType configured in the confi

      The type of the target device does not match the deviceType configured in the config.json file of the selected module. 在entry-src-main-config.json,添加tablet

    2024年02月02日
    浏览(46)
  • 探索虚拟现实:未来的互联网 browsing the virtual reality: the future of the internet

    虚拟现实(Virtual Reality,简称VR)是一种使用计算机生成的3D环境和交互方式来模拟现实世界的体验。它通过头戴式显示器(Head-Mounted Display,HMD)、手掌感应器、身体传感器等设备,使用户在虚拟环境中进行交互。随着计算机技术的不断发展,虚拟现实技术不断拓展其应用领域,成

    2024年04月13日
    浏览(40)
  • leetcode - 2830. Maximize the Profit as the Salesman

    You are given an integer n representing the number of houses on a number line, numbered from 0 to n - 1. Additionally, you are given a 2D integer array offers where offers[i] = [starti, endi, goldi], indicating that ith buyer wants to buy all the houses from starti to endi for goldi amount of gold. As a salesman, your goal is to maximize your earnings by str

    2024年02月12日
    浏览(33)
  • 【iOS】This operation can fail if the version of the OS on the device is incompatible

    Failed to prepare device for development. This operation can fail if the version of the OS on the device is incompatible with the installed version of Xcode. You may also need to restart your mac and device in order to correctly detect compatibility. 未能为开发准备设备。 如果设备上的操作系统版本与安装的 Xcode 版本不兼容,此操作

    2024年02月11日
    浏览(95)
  • 解决:The connection to the server raw.githubusercontent.com was refused - did you specify the right ho

    我在部署k8s集群安装fannel 时候 出现报错: The connection to the server raw.githubusercontent.com was refused - did you specify the right host or port? 原因:外网不可访问 解决办法: 在https://www.ipaddress.com/查询raw.githubusercontent.com的真实IP。 加入 再次运行 即可成功安装fannel 希望对各位有所帮助!

    2024年02月11日
    浏览(47)
  • The connection to the server localhost:8080 was refused - did you specify the right host or port?

    问题背景 使用 kubeadm 安装完成 kubetnetes 之后,将节点加入 master 之后,提示 The connection to the server localhost:8080 was refused - did you specify the right host or port? 问题解决 方法1 查看 /etc/kubernetes/ 目录下是否存在 kubelet.conf 或者 admin.conf (个人理解只是文件名称不同),然后将上述两个

    2024年02月11日
    浏览(54)
  • The version of CocoaPods used to generate the lockfile

    The version of CocoaPods used to generate the lockfile (1.12.1) is higher than the version of the current executable (1.11.3). Incompatibility issues may arise. 在我们使用cocoapods加载第三方库时,有时会碰到报这个错,这很明显是告诉我们现在所使用的cocoapods版本低于第三方库所要求的。 我们可以在终端中执行

    2024年02月08日
    浏览(35)
  • The method toList() is undefined for the type Stream

    The method toList() is undefined for the type Stream   (JDK16)     default ListT toList() {         return (ListT) Collections.unmodifiableList(new ArrayList(Arrays.asList(this.toArray())));     }

    2024年02月21日
    浏览(42)
  • The Material for the Project Support BloomFilter for kvrocks

    Here is the information about the project “Support BloomFilter for kvrocks” from the current web page context: Field Value 项目编号 239430147 项目难度 Advanced 支持语言 English 项目社区导师 Xuwei Fu 导师联系邮箱 maplewish117@gmail.com 技术领域 C++, Database 开源协议 Apache-2.0 License 项目简述 kvrocks is a distributed

    2024年02月07日
    浏览(26)
  • 【Spring循环依赖报错】The dependencies of some of the beans in the application context form a cycle

           类A需要通过构造函数注入的类B的实例(或者B中声明的Bean),而类B需要通过构造函数注入的类A的实例(或者A中声明的Bean),导致循环依赖注入。 其中一个不要引用对方,避免循环依赖,代码解耦肯定是最优解。 选择其中一个使用@Lazy 注解。        延迟互相

    2024年02月07日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包