菊厂机试8.3

1. 码流均分
有一段二进制码流，请将数据分为3段，每段得到相同的二进制值；
如：输入为1010010，可以分为10 10 010 3段，都表示十进制中的2.
如果无法做到，则输出-1，如果输入码流全部为0，则视作无法做到，输出-1；

输入
一串字符串，内部都为0和1的字符，最小长度为3个字节，最大长度为5*10^4个字节

输出
切分后的3段2进制数据

样例1
输入 100101000001001010000100101
输出 100101 00000100101 0000100101
解释：切分后3段都为十进制37.

//思路，如果能分为三段，则每一段的1的数目一定相同。二进制要相同，则从右向左的1的位置一定相同。
// 也就是说总的1的数目一定是3的倍数。
//设总的1数目为3*N, 两个指针i,j，一个向右，一个向左。
//左边的拥有统计第一个1和最后一个1的位置，右边统计最后一个1右边有几个0

据此从右向左，遍历三个子字符串判断相等就行。

参考代码：

int main() {
    string str;
    cin >> str;
    int n = str.size();
    int ones = 0;
    for (int i = 0; i < n; i++) {
        if (str[i] == '1') {
            ones++;
        }
    }
    if (ones % 3 != 0 || ones == 0) {
        cout << -1 << endl;
        return 0;
    }
    int s = -1, e1  = 0, e2 = 0;
    for (int i = 0, cnt = 0; cnt < 2 * ones / 3; i++ ) {
        if (s == -1 && str[i] == '1') {
            s = i;
        }
        if (str[i] == '1') {
            cnt ++;
            if (cnt == ones / 3) {
                e1 = i;
            } else if (cnt == 2 * ones / 3) {
                e2 = i;
            }
        }
    }
    int right0 = 0;
    for (int j = n - 1; str[j] != '1'; j--) {
        right0++;

    }
    //    三个数组右端点是确定的
    int k1 = e1 + right0, k2 = e2 + right0, k3 = n - 1;
    while (k1 >= s && str[k1] == str[k2] && str[k2] == str[k3]) {
        k1--;
        k2--;
        k3--;
    }
    if (k1 >= s) {
        cout << -1 << endl;
        return 0;
    }
    cout << str.substr(0, e1 + right0 + 1) << " "
         << str.substr(e1 + right0 + 1, e2 - e1) << " "
         << str.substr(e2 + right0 + 1, n - e2 - right0) << endl;
    return 0;
}

2. 薪酬统计

某公司拥有N名员工，HR按照职级从低到高（假设不存在职级相同）导出整个公司的人员薪酬数组L，当出现低级员工薪酬大于高级员工薪酬的两倍时候需要调整低级员工薪资，

调整工作由统计完成之后再进行。现在请计算整个公司需要调整的总数。

N=5000

0<L<2^31

输入

输入第一行是数组长度N，第二行是长度为N的整数数组，每个元素代表员工的薪酬，数组按照职级从低到高排列。

输出

一个整数，表示公司需要调整的总数。

例子

输入：

1 3 2 3 1

输出：

//两层暴力循环

int main () {
    int n;
    cin >> n;
    vector<int> salary(n);
    for (int i = 0; i < n; i++) {
        cin >> salary[i];
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (salary[i] > 2 * salary[j]) {
                res ++;
            }
        }
    }
    printf("res:%d\n", res);
    return 0;
}

3. 佩奇和乔治能量豆大pk

有一个盒子存放若干个能量豆，每块能量豆都有对应的能量值，能量值都是整数，用数组energyBeans表示，其中energyBeans[i]表示第i块能量豆的能力值，佩奇和乔治两个兄弟每轮PK都是任意从盒子各取一块能量豆进行PK。假如每轮PK，佩奇每次取出的能量豆的能量值为x，乔治每次取出的能量豆的能量值为y。那么PK的结果如下：

如果x==y，那么两块能量豆的能量值会被完全中和消失；

如果x!=y，则PK结果产生新的能量豆的能量值z=abs(x-y)，然后把能量值为z能量豆放回能量盒中；

经过多轮PK，最后盒子中最多只会剩下一块能量豆。返回此能量豆的最小可能能量值。

如果没有能量豆剩下，就返回0.

输入

输入是两行；

第一行是能量豆的个数n，1<=n<=10^3；

第二行是能量豆的能量值，1<=energyBeans[i]<=1000;

输出

盘子中剩余最后一块能量豆的能量值，如果没有能量豆剩下，返回0.

// 思路：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        cout<<"n:"<<n<<endl;
        if(n == 1) return stones[0];
        //问题可以转化为在stones数组加入n/2个减号使得结果最小
        //设dp[i][j]表示前i个数加入j个减号所能得到最小值
        int sum = std::accumulate(stones.begin(),stones.end(),0);
        vector<vector<bool>> dp(n+1,vector<bool>(sum,false));
        for(int j = 0;j <= sum;j++)
            dp[0][j] = false;
        dp[0][0] = true;
        //我们枚举被粉碎的石头的所有可能重量
        for(int i = 1;i <= n ;i++)
            for(int j = 0; j < sum ;j++)
            {
                if(j < stones[i-1])
                    dp[i][j] = dp[i-1][j];
                else 
                    dp[i][j] = dp[i-1][j-stones[i-1]] || dp[i-1][j];
                // printf("i:%d, j%d,dp:%d\n",i,j,dp[i][j]?1:0);
            }
        int res = sum;
        for(int j = 0;j < sum;j++)
        if(dp[n][j]&& sum >= 2*j) res = min(res, sum-2*j);
        return res;
    }
};

leetcode 1049