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

#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  */