sicily 10359 Valuable Jewellery

2023-12-12 14:59

本文主要是介绍sicily 10359 Valuable Jewellery,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

贪心

题意:
背包问题,n个物品,有重量有价值.不同的是,有k个背包,每个背包有重量上限,且最多只能放一个物品.问最大价值

数据范围:
n,k<=300000,重量,价值<=10^6,背包上限<=10^8

思路:

每个背包最多只能放一个物品,那这题一下子就水了

贪心,背包用一个map存放,物品按价值递减排序.扫描每个物品,每次在map里找这个物品的质量的下界,有的话就更新答案,维护map,无的就只能放弃了

总结:贪心,优先选择物品价值高的


这篇关于sicily 10359 Valuable Jewellery的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/485019

相关文章

sicily 分类

原文出处:http://linguifan2010.blog.163.com/blog/static/1315127442010102131322482/ *************************程序设计题************************* *************************数据结构************************* sicily

uva 10359 Tiling

原题: In how many ways can you tile a 2 × n rectangle by 2 × 1 or 2 × 2 tiles?Here is a sample tiling of a 2 × 17 rectangle. Input Input is a sequence of lines, each line containing an integer numb

sicily 1225. 电子眼

/图其实是一个树加了一条边,我们找到这个环,然后枚举其中一条边的两端,看是在哪里安装电子眼。剩下的就是普通的树形dp了。。 #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int MAXN = 101000; vector<

sicily 4425Easy Sort

进行一次翻转之后,接下的翻转肯定只交换相邻的数,统计逆序对。 用树状数组做,新序列保存在arr中, 没读入一个arr[i],就在c[arr[i]]位置加1,这时候arr[i]与之前输入的i个数中构成逆序的就是i-sum(arr[i])拉。。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm

sicily 4876. PLAĆE 每周一赛二

树形结构转线性结构,先dfs,得到每一个结点的开始和结束访问时间s,t 记录一个数组A[1...t] 那么更新一个结点的就是A[s]+=v,A[t]-=v 采用树状数组做,OMlog2*N复杂度 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector>

sicily 1876. Basic Graph Problem 线段树+并查集+路径压缩

线段树或者RMQ都可以做,虽然是不是动态变化的,但是用线段树做也不错,,而且最近才开始弄线段树,当练练手。。。 一定要路径压缩的并查集,,不然线性的话,耗时过高。。。 而且不能写递归的路径压缩,我猜得。。。 因为n<=100000,一般20000就会栈爆的,,,, #include<iostream> #include<cstdio> #include<cstring> using

Sicily 1099 Packing Passengers

Constraints Time Limit: 1 secs, Memory Limit: 32 MB Description PTA, Pack ‘em Tight Airlines is attempting the seemingly impossible—to fly with only full planes and still make a profit. Their strategy

Arpa's weak amphitheater and Mehrdad's valuable Hoses

背包问题?!+并查集 一组朋友之中最多只能有一个人去,所以需要在写0-1背包时需要调整for循环的顺序 错解: for(int i=1;i<=n;i++){sum_b=0,sum_w=0;if(pre[i]==i){for(int j=0;j<vn[i].size();j++){sum_b+=bn[vn[i][j]];sum_w+=wn[vn[i][j]];for(int k=w;k>=

Sicily Shortest path in unweighted graph

Source: http://soj.sysu.edu.cn/show_problem.php?pid=1003&cid=2104 Description 输入一个无向图,指定一个顶点s开始bfs遍历,求出s到图中每个点的最短距离。 如果不存在s到t的路径,则记s到t的距离为-1。 Sample Input 输入的第一行包含两个整数n和m,n是图的顶点数,m是边数。1<=n<=1000

Sicily Connect components in undirected graph

Source: http://soj.sysu.edu.cn/show_problem.php?pid=1002&cid=2104 Description 输入一个简单无向图,求出图中连通块的数目。 Sample Input 输入的第一行包含两个整数n和m,n是图的顶点数,m是边数。1<=n<=1000,0<=m<=10000。 以下m行,每行是一个数对v y,表示存在边(v,y)。顶