美团8.19 ak

不保证代码能跑，代码是从clion的历史版本扒出来的不一定是最后提交的版本

第一题，忘了，文件也找不到了pass

第二题，

#include<iostream>
#include "algorithm"
#define ll long long
using namespace std;

int main(){
     ll n;
     cin>>n;

     ll sum = 0;
     ll* values = new ll[n];
     for(int i = 0 ; i < n; ++i){
         cin >> values[i];
         sum += values[i];
     }
     ll maxgain = 0;
     for(int i = 0 ; i < n - 1 ; ++i){
         ll gain = values[i]*values[i+1] - values[i] - values[i+1];
         maxgain = max(maxgain, gain);
     }
     cout<<sum + maxgain<<endl;
}

第三题，注意到合法的串只能是010101或者101010就很简单

#include<iostream>
#include "algorithm"
#include "string"
#define ll long long
#include "vector"
using namespace std;

int main(){
    string s;
    cin >> s;
    ll count = 0;
    ll size = s.size();
    vector<vector<ll>> dp1(size, vector<ll>(size, 0));
    vector<vector<ll>> dp2(size, vector<ll>(size, 0));

    for(int i = 0 ; i < size ; ++i){
        if(i%2 == 1){
            if(s[i] == '0'){
                dp1[i][i] = 1;
            }else{
                dp2[i][i] = 1;
            }
        }else{
            if(s[i] == '1'){
                dp1[i][i] = 1;
            }else{
                dp2[i][i] = 1;
            }
        }
    }

    for(int i = 0 ; i < size; ++i){
        for(int j = i+1 ; j < size; ++j){
            if(j%2 == 0){
                if(s[j] == '1'){
                    dp1[i][j] = dp1[i][j-1] + 1;
                    dp2[i][j] = dp2[i][j-1];
                }else{
                    dp2[i][j] = dp2[i][j-1] + 1;
                    dp1[i][j] = dp1[i][j-1];
                }
            }else{
                if(s[j] == '1'){
                    dp2[i][j] = dp2[i][j-1] + 1;
                    dp1[i][j] = dp1[i][j-1];
                }else{
                    dp1[i][j] = dp1[i][j-1] + 1;
                    dp2[i][j] = dp2[i][j-1];
                }
            }

            count += min(dp1[i][j], dp2[i][j]);
        }
    }

    cout << count;
    return 0;
}

第四题，dp，前i位分配j个有多少种分配方法

#include "iostream"
#include "vector"
#define ll long long
#define base 1000000007
using namespace std;

int main(){
    int n;
    cin >> n;

    int* a = new int[n];
    int suma = 0;
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i];
        suma += a[i];
    }

    vector<vector<ll>> dp(n, vector<ll>(suma+1, 0));
    for(int i = 1 ; i < suma; ++i){
        if(i!=a[0])
            dp[0][i] = 1;
    }
    for(int i = 1; i < n; ++i){
        for(int j = i + 1; j <= suma; ++j){
            ll count = 0;
            for(int front = 1; front < j; ++front){
                if(j - front != a[i])
                    count = (count + dp[i-1][front]) % base;
            }
            dp[i][j] = count;
        }
    }
    cout << dp[n-1][suma];
}

第五题，分类讨论，能平均就得把所有数据变成一样的，不能平均就需要舍弃一个，把其余的变成一样的，舍弃的应当是最大值或者最小值，剩余的数字变成剩余数字的平均值（向下取整以及向下取整加一都有可能）

#include<iostream>
#include "algorithm"
#include "string"
#define ll long long
#include "vector"
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<ll> a(n, 0);
    ll ssum = 0;

    for(int i = 0 ; i < n ; ++i){
        cin >> a[i];
        ssum += a[i];
    }

    ll count = 0;
    if(ssum % n == 0){
        ll avg = ssum / n;
        for(auto it: a){
            if(it > avg){
                count += (it - avg);
            }
        }
        cout << count << endl;
    }else{
        // 需要抛弃一个值
        ll toPrint;
        sort(a.begin(), a.end());
        //放弃第一个
        ll sumWithoutFirst = 0;
        for(int i = 1 ; i < n; ++i){
            sumWithoutFirst += a[i];
        }
        ll newAvg = sumWithoutFirst / (n-1);
        ll changeNeg = 0, changePos = 0;
        for(int i = 1 ; i < n; ++i){
            if(a[i] > newAvg){
                changePos += (a[i]-newAvg);
            }else{
                changeNeg += (newAvg - a[i]);
            }
        }
        toPrint = max(changeNeg, changePos);

        changeNeg = 0, changePos = 0;
        newAvg ++;
        for(int i = 1 ; i < n; ++i){
            if(a[i] > newAvg){
                changePos += (a[i]-newAvg);
            }else{
                changeNeg += (newAvg - a[i]);
            }
        }
        toPrint = min(toPrint, max(changeNeg, changePos));

        // 抛弃最后一个
        ll sumWithoutLast = 0;
        for(int i = 0 ; i < n-1; ++i){
            sumWithoutLast += a[i];
        }
        newAvg = sumWithoutLast / (n-1);

        changeNeg = 0, changePos = 0;
        for(int i = 0 ; i < n-1; ++i){
            if(a[i] > newAvg){
                changePos += (a[i]-newAvg);
            }else{
                changeNeg += (newAvg - a[i]);
            }
        }
        toPrint = min(toPrint, max(changeNeg, changePos));

        newAvg++;
        changeNeg = 0, changePos = 0;
        for(int i = 0 ; i < n-1; ++i){
            if(a[i] > newAvg){
                changePos += (a[i]-newAvg);
            }else{
                changeNeg += (newAvg - a[i]);
            }
        }
        toPrint = min(toPrint, max(changeNeg, changePos));
        cout<<toPrint;
    }
}