UVa12834 - Extreme Terror(水題)

題目大意

Shamsu 有幾個商業地點，這些地點分別都會帶來收益，但這些商業地點都有房租。
房東們全都是同一人，房東讓你選 k 個地點(不一定要選到 k，可以小於 k)不需要收租、也不能帶來利益。

我們想請你幫幫忙，幫助 Shamsu 獲得最大的利益。
其中利益計算方法為：\(收益 - 房租\)。

題目連結

重點觀念

• 水題，英文太長，不好閱讀八XD

分析

• 這題其實不難，就是先計算每一個商業地點的利益
• 之後 sort
• 選擇 k
  • 將利益最小的(負數)，都刪掉，直到放棄的地點數量 = k
  • 利益如果為正，全部保留。
    因為利益只要為正，即是在小都會讓 Shamsu 獲得更多利益

心得

這題沒有很難，就是普通的水題。考我英文測驗XD

參考連結

Uva12834 - Extreme Terror by txya900619

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1000020
#define int long long
using namespace std;
int t, n, k, kase = 0;
int profit[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> k;
        for(int i = 0; i < n; i++){ //輸入成本
            cin >> profit[i];
            profit[i] *= -1;
        }
        int y;
        for(int i = 0; i < n; i++){ //輸入獲利，並計算利益
            cin >> y;
            profit[i] += y;
        }
        sort(profit, profit+n); //排序，由小排到大

        int ans = 0;
        for(int i = 0; i < n; i++){ 
            if(k && profit[i] < 0){ //獲利為負，並且還有額度可以放棄
                k--;
                continue;
            }
            ans += profit[i]; //計算在總獲利中
        }

        //輸出答案
        if(ans > 0) cout << "Case " << ++kase << ": " << ans << '\n';
        else cout << "Case " << ++kase << ": No Profit" << '\n';
    }
    return 0;
}