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

　　特此记录一下：

 

　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 
     
      #include 
      
       #include 
       
        #include 
        
         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
         
           Tuple;bool cmp(const Tuple a, const Tuple b) {    return a.second < b.second;}multiset
          
            s1, s2;multiset
           
            ::iterator it;multiset
            
             ::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 22 34 15 71 36 3*/