c/c++语言开发共享一道有意思的思维题 — 排序、枚举

这道题是在与学弟吃饭的路上听学弟讲的,感觉挺有意思的,需要不少的思维(可能我长时间没有刷题了,有点笨了~) 特此记录一下: Problem: 有n个(x,y)元组,求从中取出k个元组,使得这k个元组的x之和乘以其中最小的y值的值最大 ( sum(x)*min(y) in k个元组 ) Solutio …

 

  这道题是在与学弟吃饭的路上听学弟讲的,感觉挺有意思的,需要不少的思维(可能我长时间没有刷题了,有点笨了~)

  特此记录一下:

 

 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.ctvol.com/c-cdevelopment/601616.html

(0)
上一篇 2021年5月10日
下一篇 2021年5月10日

精彩推荐