题目

题目地址

给定两个长度为 n 的 01 数组 a1,a2,…,an 和 b1,b2,…,bn。

请你构造一个长度为 n 的正整数数组 p1,p2,…,pn。

要求
∑ai×pi>∑bi×pi
成立。

此外，max pi 需要尽可能小。

输出最小可能值。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含 n 个整数 b1,b2,…,bn。

输出格式

输出 max pi 的最小可能值。

如果不存在满足条件的数组 p，则输出 −1。

数据范围

1≤n≤100
0≤ai,bi≤1

输入样例1：

5
1 1 1 0 0
0 1 1 1 1

输出样例1：

3

输入样例2：

3
0 0 0
0 0 0

输出样例2：

-1

输入样例3：

4
1 1 1 1
1 1 1 1

输出样例3：

-1

输入样例4：

9
1 0 0 0 0 0 0 0 1
0 1 1 0 1 1 1 1 0

输出样例4：

4

思路

我们知道a,b数组是只有0和1构建的，那么就存在如下四种情况。

a	b
1	0
0	1
0	0
1	1

根据上面四种情况，我们可以发现，当a b数值一样时，无论p为多少，是产生不了a * p 和 b * p的差值的，也就是说决定着差值的是 01 和 10的个数，当a 为 1,b 为 0这种情况不存在的时候，我们无论如何也做不到题目要求的a * p > b * p，所以只有当10存在的情况下，我们才可以调整数值pi来达到题目要求。

那么如何调整p值呢？ 我们可以现假设所有p为1，因为一旦存在，p最小为1，当10的数量大于01时，p不需要调整，如果10数量小于等于01时，此时就需要调整了，为了让最大值最小，那么就尽可能让每个p值都去调动，例如差值为8时，10的数量为2，此时我们需要将使得a * p > b * p 我们就需要来弥补差值并+1,也就是说调动p 使得前面数列的和增加9，我们把9分摊给每个10下的pi，此时p 为 5（初始值为1），此时差值还剩1，但不足以每个去分担，只要让部分去分担即可，那么最大的值就是6。

代码

#include<iostream>
using namespace std;
const int N = 100 + 10;
int n;
int a[N], b[N];

int main() {
    cin >> n;
    int x = 0, y = 0, p = 1;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    for(int i = 0; i < n; i++) {
        if(a[i] && !b[i]) x++;
        if(!a[i] && b[i]) y++;
    }
    if(!x) cout << -1 << endl;
    else if(x > y) cout << 1 << endl;
    else {
        int z = y - x + 1;
        p += z / x;
        z %= x;
        if(z) p++;
        cout << p << endl;
    }
    return 0;
}