当前位置:网站首页>[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 ).
边栏推荐
- Penetration test (7) -- vulnerability scanning tool Nessus
- Web based photo digital printing website
- Opencv learning log 14 - count the number of coins in the picture (regardless of overlap)
- 信息安全-威胁检测引擎-常见规则引擎底座性能比较
- Accounting regulations and professional ethics [4]
- Accounting regulations and professional ethics [1]
- 编程到底难在哪里?
- 通俗地理解什么是编程语言
- If you want to apply for a programmer, your resume should be written like this [essence summary]
- mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
猜你喜欢
Information security - Analysis of security orchestration automation and response (soar) technology
用C语言写网页游戏
Borg Maze (BFS+最小生成树)(解题报告)
程序员的你,有哪些炫技的代码写法?
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
Gartner:关于零信任网络访问最佳实践的五个建议
动态规划前路径问题优化方式
STM32 learning record: LED light flashes (register version)
C语言是低级和高级的分水岭
Matlab example: two expressions of step function
随机推荐
渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
Cost accounting [19]
信息安全-威胁检测引擎-常见规则引擎底座性能比较
用C语言写网页游戏
China earth moving machinery market trend report, technical dynamic innovation and market forecast
力扣刷题记录
nodejs爬虫
Research Report on market supply and demand and strategy of China's land incineration plant industry
Cost accounting [17]
【练习-6】(PTA)分而治之
数据在内存中的存储&载入内存,让程序运行起来
Research Report on shell heater industry - market status analysis and development prospect forecast
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志
Essai de pénétration (1) - - outils nécessaires, navigation
[exercise-7] crossover answers
最全编程语言在线 API 文档
[exercise-6] (PTA) divide and conquer
STM32 how to use stlink download program: light LED running light (Library version)