一道有意思的思維題 --- 排序、列舉-有解無憂

　　這道題是在與學弟吃飯的路上聽學弟講的，感覺挺有意思的，需要不少的思維（可能我長時間沒有刷題了，有點笨了~）

　　特此記錄一下：

　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.uj5u.com/houduan/100179.html

標籤：C++

上一篇：MSF基礎與應用

下一篇：插入排序