第一題：貪心（100分）

給一個數(shù)組arr，每次選下標(biāo)i和j，對arr[i]-=1,arr[j]+=1.如果i<j,這操作免費，否則消耗一個金幣。

數(shù)組長度1e5，數(shù)組的和為0.求最小對少消耗能使得所有元素變成0.

貪心思路：用ans表示消耗，用acc表示目前的累加值，順序迭代

當(dāng)acc為正時，表示當(dāng)前有剩余的可以用于自減（操作免費的次數(shù)）

當(dāng)acc為負(fù)時，表示需要消耗金幣才能實現(xiàn)的操作（收費操作的次數(shù)）

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        ll ans = 0, acc = 0;
        int tmp;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &tmp);
            acc += tmp;
            if (acc < 0)
            {
                ans -= acc;
                acc = 0;
            }
        }
        cout << ans << endl;  
    }
    return 0;
}

第二題：貪心（100分）

lc11.但是數(shù)據(jù)里1e7，并且沒有輸入數(shù)據(jù)的個數(shù)，數(shù)據(jù)多行，數(shù)據(jù)之間用','和' '隔開，主要是處理數(shù)據(jù)輸入

用while (cin >> str)處理不定行

對于每行，先用stringstream按照','隔開，然后判斷是不是存在非' '的字符(空的字符串或者全是' '組成的字符串調(diào)用stoi會報異常）

g++ wenyuan2.cpp && ./a.out 
terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoi
Aborted

然后就是頭尾雙指針貪心求解，用long long存。

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main()
{
    string str;
    vector<int> arr;
    while (cin >> str)
    {
        stringstream ss(str);
        string tmp;
        while (getline(ss, tmp, ','))
        {
            if (tmp.find_first_not_of(' ') != string::npos)
                arr.push_back(stoi(tmp));
        }
    }
    int n = arr.size();
    int l = 0, r = n - 1;
    ll ans = 0;
    while (l < r)
    {
        ans = max(ans, ll(r - l) * min(arr[l], arr[r]));
        if (arr[l + 1] >= arr[r - 1])
            l++;
        else
            r--;
    }
    cout << ans << endl;
    return 0;
}

第三題：不會寫（14.29分）

就騙了一點分（寫第三題時還有一個半小時，但完全不會，連暴力解的思路都沒有）