当前位置:网站首页>[exercise-9] Zombie's Treasury test
[exercise-9] Zombie's Treasury test
2022-07-06 15:56:00 【Flame car】
The main idea of the topic :
Some brave soldiers came to a lost village . They are very lucky , Found many treasures and a big treasure chest , But also found angry zombies .
The soldiers are very brave , They decided to defeat the zombies , Then bring back all the treasures . A long and brutal battle continued from morning till night , The soldiers found that zombies are immortal , Invincible .
Of course , The treasure should not be left here . Unfortunately , Due to the limitation of treasure chest capacity , Soldiers can't carry all the treasures in treasure chest . in fact , There are only two kinds of treasures : Emeralds and Sapphires . All emeralds are equal in size and value , And the number is infinite . Sapphire, too .
As a priest of soldiers with magical artifacts : The computer , Considering the size of the box , The value and size of each gem , You should calculate the maximum value of the treasure that our soldiers can bring back .
AC Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
struct node{
ll s,v;
};
node mx,mn,a[2];
int main()
{
int t,V;
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>V>>a[0].s>>a[0].v>>a[1].s>>a[1].v;
ll t1 = a[0].v*a[1].s;
ll t2 = a[1].v*a[0].s;
ll res = 0;
if(t1>=t2)
mx.s=a[0].s,mx.v=a[0].v,mn.s=a[1].s,mn.v=a[1].v;
else
mx.s=a[1].s,mx.v=a[1].v,mn.s=a[0].s,mn.v=a[0].v;
ll top = V/mn.s;
top = min(top,mx.s-1);
for(ll j=0;j<=top;j++)
{
ll tmp1=j*mn.v;
ll tmp2=(V-j*mn.s)/mx.s*mx.v;
res = max(res,tmp1+tmp2);
}
printf("Case #%d: %lld\n",i,res);
}
return 0;
}
What this problem simplifies is to take the range of the number of low value items .
First , We know :
The volume of the box is V
Every item 1 The volume of is s1, The value is v1.
Every item 2 The volume of is s2 , The value is v2.
Then there should be s2 Items 1 when , goods 1 The volume of is s2 * s1, The value is s2 * v1.
Similarly, there should be s1 Items 2 when , goods 2 The volume of is s1 * s2, The value is s1 * v2.
Obviously at this time : goods 1 Volume = goods 2 Volume , and goods 1 The value of Not necessarily equal to goods 2 The value of .
Let's assume that the objects in the same volume 1 Higher value :
That is to say, the volume is the same ,s2 * v1 > s1 * v2.
On the other hand , When there is s1 Items 2 His value must be lower than s2 Items 1, So the object 2 The quantity of must be less than s1 Of .
in other words , goods 1 Take as much as possible , And objects 2 Most take s1-1 individual .
Of course, this is not the simplest , Obviously take the least common multiple lcm Time items 2 Get fewer ( Less time complexity ).
边栏推荐
- C语言学习笔记
- Research Report on shell heater industry - market status analysis and development prospect forecast
- Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
- Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
- 用C语言写网页游戏
- VS2019初步使用
- E. Breaking the Wall
- [exercise-2] (UVA 712) s-trees
- CEP used by Flink
- Ball Dropping
猜你喜欢
B - 代码派对(女生赛)
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
Penetration test (3) -- Metasploit framework (MSF)
D - Function(HDU - 6546)女生赛
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Borg Maze (BFS+最小生成树)(解题报告)
【高老师UML软件建模基础】20级云班课习题答案合集
【练习-7】Crossword Answers
【高老师软件需求分析】20级云班课习题答案合集
STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
随机推荐
Cost accounting [18]
Truck History
Information security - security professional name | CVE | rce | POC | Vul | 0day
Flink 使用之 CEP
Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
渗透测试 ( 1 ) --- 必备 工具、导航
渗透测试 ( 4 ) --- Meterpreter 命令详解
Nodejs+vue网上鲜花店销售信息系统express+mysql
C语言是低级和高级的分水岭
Indonesian medical sensor Industry Research Report - market status analysis and development prospect forecast
Web based photo digital printing website
Perinatal Software Industry Research Report - market status analysis and development prospect forecast
[exercise-2] (UVA 712) s-trees
Cost accounting [13]
B - 代码派对(女生赛)
Accounting regulations and professional ethics [3]
初入Redis
Matlab example: two expressions of step function
Essai de pénétration (1) - - outils nécessaires, navigation
7-1 懂的都懂 (20 分)