当前位置:网站首页>Hj16 shopping list
Hj16 shopping list
2022-07-05 23:00:00 【ChasnyChang】
describe
Wang Qiang is very happy today , The company issued N A year-end bonus of yuan . Wang Qiang decided to use the year-end bonus for shopping , He divided the items he wanted to buy into two categories : Main parts and accessories , The attachment is subordinate to a main component , Here are some examples of main components and accessories :
Main parts | The attachment |
The computer | The printer , Scanner |
Bookcase | The book |
desk | Desk lamp , Stationery |
Work chair | nothing |
If you want to buy items classified as accessories , You must buy the main part of the accessory first , And each item can only be purchased once . Each main component can have 0 individual 、 1 Or 2 Attachments . Attachments no longer have their own attachments . Wang Qiang wants to buy a lot of things , In order not to exceed the budget , He set an importance level for each item , It is divided into 5 etc. : Integers 1 ~ 5 Express , The first 5 And so on . He also looked up the price of each item on the Internet ( All are 10 An integral multiple of one yuan ). He hopes not to exceed N element ( Can be equal to N element ) Under the premise of , To maximize the sum of the product of the price of each item and its importance .
Set the first j The price of the item is v[j] , The importance is w[j] , A total of k Item , The serial numbers are j 1 , j 2 ,……, j k , Then the sum of the requirements is :
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] .( among * For the multiplier )
Please help Wang Qiang design a shopping list that meets the requirements .
Input description :
Input the 1 That's ok , For two positive integers , Separated by a space :N m
( among N ( <32000 ) It means the total amount of money , m ( <60 ) For the number of items you want to buy .)
From 2 Go to the first place m+1 That's ok , The first j Line gives the number j-1 The basic data of the items , Each row has 3 Nonnegative integers v p q
( among v Indicates the price of the item ( v<10000 ), p Indicates the importance of the item ( 1 ~ 5 ), q Indicates whether the item is a master or an accessory . If q=0 , It means that the article is the main component , If q>0 , It means that the article is an accessory , q Is the number of the main part )
Output description :
The output file has only one positive integer , It is the maximum value of the sum of the product of the price and importance of the goods that does not exceed the total amount of money ( <200000 ).
Example 1
Input :
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
Copy output :
2200
Copy
Example 2
Input :
50 5 20 3 5 20 3 5 10 3 0 10 2 0 10 1 0
Copy output :
130
Copy instructions :
From the first 1 OK, you can see the total money N by 50 And the number of items you want to buy m by 5; The first 2 And the 3 Yes q by 5, Explain that they are all numbered 5 The attachment of the item ; The first 4~6 Yes q All for 0, It means that they are all main parts , Their numbers are 3~5; Therefore, the maximum value of the sum of the product of the price and importance of an article is 10*1+20*3+20*3=130
The test case passed , When submitting the following set of data, the answer is 3900, But manual calculation is 3500
1000 5
300 5 0
400 2 0
300 5 2
300 4 2
600 4 0
Optimization welcome ~
#include<bits/stdc++.h>
using namespace std;
// List of each item entered
struct Node {
int Val; // The unit price
int Money; // The unit price * The weight The sum of the
};
// The unit price * Weight ranking
bool cmp(Node node1, Node node2)
{
return node1.Money > node2.Money;
}
int main()
{
int money, Num, count = 0;
cin >> money >> Num;
int i = Num;
// Definition Num An array of structures
Node* node = new Node[Num];
for (int i = 0; i < Num; i++)
{
node[i].Val = 0;
node[i].Money = 0;
}
while (i)
{
int val, weight, num;
cin >> val >> weight >> num;
// assignment
if (num == 0)
{
node[Num - i].Val += val;
node[Num - i].Money += val * weight;
}
else
{
node[num - 1].Val += val;
node[num - 1].Money += val * weight;
}
i--;
}
// Sort by total value from large to small
sort(node, node + Num, cmp);
//i = 0;
for (int j = 0;j < Num; j++)
{
if (i + node[j].Val > money)
continue;
else
{
i += node[j].Val;
count += node[j].Money;
}
}
cout << count;
return 0;
}
边栏推荐
- 我对新中台模型的一些经验思考总结
- leecode-学习笔记
- 抖音__ac_signature
- 实现反向代理客户端IP透传
- audiopolicy
- Marginal probability and conditional probability
- 从 1.5 开始搭建一个微服务框架——日志追踪 traceId
- The code generator has deoptimised the styling of xx/typescript.js as it exceeds the max of 500kb
- Roman numeral to integer
- Element positioning of Web Automation
猜你喜欢
[speech processing] speech signal denoising and denoising based on MATLAB low-pass filter [including Matlab source code 1709]
Marginal probability and conditional probability
[speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
两数之和、三数之和(排序+双指针)
TCC of distributed solutions
2022 registration examination for safety management personnel of hazardous chemical business units and simulated reexamination examination for safety management personnel of hazardous chemical busines
Metaverse ape received $3.5 million in seed round financing from negentropy capital
如何快速理解复杂业务,系统思考问题?
Ultrasonic sensor flash | LEGO eV3 Teaching
Negative sampling
随机推荐
Nangou Gili hard Kai font TTF Download with installation tutorial
How can easycvr cluster deployment solve the massive video access and concurrency requirements in the project?
Evolution of APK reinforcement technology, APK reinforcement technology and shortcomings
Binary tree (III) -- heap sort optimization, top k problem
Fix the memory structure of JVM in one article
Metaverse ape received $3.5 million in seed round financing from negentropy capital
Function default parameters, function placeholder parameters, function overloading and precautions
[screen recording] how to record in the OBS area
[speech processing] speech signal denoising and denoising based on MATLAB low-pass filter [including Matlab source code 1709]
Openresty ngx Lua regular expression
视频标准二三事
Leetcode daily question 1189 The maximum number of "balloons" simple simulation questions~
openresty ngx_ Lua regular expression
Finally understand what dynamic planning is
Vcomp110.dll download -vcomp110 What if DLL is lost
Global and Chinese markets for children's amusement facilities 2022-2028: Research Report on technology, participants, trends, market size and share
513. Find the value in the lower left corner of the tree
一文搞定class的微观结构和指令
Ultrasonic sensor flash | LEGO eV3 Teaching
audiopolicy