一道有意思的思维题 --- 排序、枚举
2019-10-08 08:47:19来源:博客园 阅读 ()
一道有意思的思维题 --- 排序、枚举
这道题是在与学弟吃饭的路上听学弟讲的,感觉挺有意思的,需要不少的思维(可能我长时间没有刷题了,有点笨了~)
特此记录一下:
Problem:
有n个(x,y)元组,求从中取出k个元组,使得这k个元组的x之和乘以其中最小的y值的值最大 ( sum(x)*min(y) in k个元组 )
Solution:
将n个元组按照y值从小到大排序,然后从小到大枚举每个y值,以当前的y值为选取的k个元组中的最小值,那么k个元组位于当前元组之后(一定包含当前元组)。也就是说,有k-1个元组还未确定,需要从当前元组之后选 取 k-1个最大的x值对应的元组。那么问题简化为从当前元组后取k-1个最大的数。计算出sum_i(x)*min_i(y),i为当前元组的index, 取最大值就是正确的答案了。
为了提高枚举转移的速度,我们用两个集合来维护i+1-n的元组中最大的k-1个x之和。set2中存储最大的k-1个x,set1中存储剩余的x(index=i+1~n的元组),这样转移的时候需要判断元组[i+1].x是否在set1中,在则直接剔 除;否则一定在set2中,则需要剔除,并从set1中取出最大的x,当然取出后set1需要剔除这个x。
代码如下:
#include <iostream> #include <algorithm> #include <string> #include <set> using namespace std; //Problem: 有n个(x,y)元组,求从中取出k个元组,使得这k个元组的x之和乘以其中最小的y值的值最大 ( sum(x)*min(y) in k个元组 ) //Solution: 将n个元组按照y值从小到大排序,然后从小到大枚举每个y值,以当前的y值为选取的k个元组中的最小值,那么k个元组位于当前元组之后(一定包含当前元组)。也就是说 // 有k-1个元组还未确定,需要从当前元组之后选取k-1个最大的x值对应的元组。那么问题简化为从当前元组后取k-1个最大的数。计算出sum_i(x)*min_i(y),i为当前元组的 // index, 取最大值就是正确的答案了。 // 为了提高枚举转移的速度,我们用两个集合来维护i+1-n的元组中最大的k-1个x之和。set2中存储最大的k-1个x,set1中存储剩余的x(index=i+1~n的元组),这样转移的 // 时候需要判断元组[i+1].x是否在set1中,在则直接剔除;否则一定在set2中,则需要剔除,并从set1中取出最大的x,当然取出后set1需要剔除这个x。 const int N = 1e5 + 5; typedef pair<int, int> Tuple; bool cmp(const Tuple a, const Tuple b) { return a.second < b.second; } multiset<int> s1, s2; multiset<int>::iterator it; multiset<int>::reverse_iterator rit; int main() { int n, k; cin >> n >> k; Tuple data[N]; for (int i = 0; i < n; i++) { cin >> data[i].first >> data[i].second; } sort(data, data + n, cmp); for (int i = 1; i < n; i++) { s1.insert(data[i].first); } int ans = 0; int sum = 0; for (int i = 1; i < k; i++) { int max_val = *s1.rbegin(); s1.erase(s1.find(max_val)); s2.insert(max_val); sum += max_val; } for (int i = 0; i +k-1< n; i++) { ans = max(ans, data[i].second*(sum+data[i].first)); if (n - i == k) break; if (s1.count(data[i+1].first) >0) { it = s1.find(data[i+1].first); s1.erase(it); } else { it = s2.find(data[i+1].first); sum -= *it; s2.erase(it); rit = s1.rbegin(); sum += *rit; s2.insert(*rit); s1.erase(s1.find(*rit)); } } std::cout << "Answer = " << ans << endl; return 0; } /* 5 2 2 3 4 1 5 7 1 3 6 3 */
原文链接:https://www.cnblogs.com/chen9510/p/11613849.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 朋友(翻转树边权值比赛)——依然是思维 2020-04-12
- Emergency Evacuation(最短下车时间)———(思维) 2020-04-11
- 翻转字符串里面的单词 2020-04-10
- 母牛的故事 2020-02-16
- 二进制枚举之被RE完虐的我的一天 2020-01-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash