Codeforces Round #697 (Div. 3) D. Cleaning the Phone（1800）

Codeforces 1475 D. Cleaning the Phone

題目大意：

給你三行

第一行 n , m：n代表軟體數，m代表要清理出來的記憶體

第二行有n個資料，每個資料代表該軟體所占用的記憶體

第三行還是n個資料，每個資料代表軟體的重要程度，隻有1和2，2更重要一點

題目要求輸出，清理出來m記憶體的前提下，删去軟體重要程度點盡可能小

思路分析：

上來一看，很快啊，感覺是個貪心，但是感覺處理的條件有點多，這個東西隻要想明白了過程還蠻好了解的QWQ。

我的想法是：重要程度 1 和 2 軟體 分開存，然後 1 從小到大排序，2 從大到小排序，友善後續過程。然後先計算全部的 1，之後在對 2 進行一個一個考慮（相當于暴力枚舉了）并且每個符合題意的重要程度點數都存進 set 中，最後隻要取出set中的第一個元素的值即可。

AC代碼：

#include <algorithm>
#include <iostream>
#include <set>
 
#define ll long long
 
using namespace std;
 
const int N = 2 * 1e5 + 10;
 
int n, m;
int one[N];
int two[N];
int flag[N];
int num[N];
set<int> s;
int j,k;
int p;
ll sum,res;
 
bool cmp(int n, int m) {
    return n > m;   // n > m 就是從大到小   n < m 就是從小到大
}
 
void fun () {
    while(sum > m && p < j) {
        sum -= one[p++];
        res--;
        if(sum >= m)
            s.insert(res);
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> num[i];
            sum += num[i];
        }
        for (int i = 0; i < n; i++)
            cin >> flag[i];
        j = 0, k = 0;
        for (int i = 0; i < n; i++) {
            if (flag[i] == 1)
                one[j++] = num[i];
            else
                two[k++] = num[i];
        }
 
        sort(one, one + j);
        sort(two, two + k, cmp);
 
        bool flag = true;
        if (sum < m)
            flag = false;
 
        sum = 0;
        for (int i = 0; i < j; i++)
            sum += one[i];
        res = j;
        p = 0;
        if(sum >= m)
            s.insert(res);
        // 如果沒有 重要程度為 2 的情況，進行的處理
        fun();
        for (int i = 0; i < k; i++) {
            fun();
            sum += two[i];
            res += 2;
            if(sum >= m)
                s.insert(res);
            fun();
        }
        if (flag)
            cout << *s.begin() << endl;
        else
            cout << -1 << endl;
        s.clear();
    }
    return 0;
}
           

彩蛋：

比賽的時候。。。思路是有，但是代碼實作搞不出來QWQ，賽後補題冷靜下來感覺能敲出來，還是自己碼力不夠嗚嗚嗚QAQ

個人感覺多重背包的闆子也能做出來（但還沒有嘗試。。。。後期可能會補這個坑