You have N voters, each with a vote (0 or 1) and a...

Question

You have N voters, each with a vote (0 or 1) and a weight w[i].

K0666

You may flip up 1 or 1 to dani votes (change 0-

After flipping, candidate 1 wins if the total weight of votes for 1 is strictly greater than the total weight of votes for 0.

Determine whether candidate 1 can win, and if so, return the minimum number of flips needed. Return -1 if candidate 1 cannot win even with K flips.

Find the minimum flips for candidate 1 to win, or -1 if impossible.

Input Format

0666

The first line contains a integer, n, denoting the number of votes.

The second line contains a integer, k, denoting the maximum number of vote flips allowed.
Each line i of the n subsequent lines (where 0 <= i < n ) contains a integer, v[i].

Each line i of the n subsequent lines (where 0 <= i < n ) contains a integer, w[i].

Constraints

1 <= n <= 10 ^ 5

1 <= k <= 10 ^ 5

nish06

10 ^ 9 <= v[i] <=10^ ^9
10 ^ 9 <= w[i] <=10^ ^9

Sample Test Cases

Case 1

Input:

3

1

1
0
10
5
10
Output
0
Explanation:

Explanation: S

1

=10+10=20, S

lidanish0666

0

Since 2035 winning. Candidate 1 is already

Case 2

Input:

4

2

0

1

10

20

5

Output

1

14

Explanation:

5

1

S
0
-1042045-35. To win with minimum flips, we flip theo with the largest weight (20). Now S 1

5+20-25 and S

0

alidanish0666

-35-20-15. 25>15, so Candidate 1 wins after 1 flip.

Case 3

Input:

3

1

0

100

100
Output
-1
Explanation:

S 1

=0, S 0

=300. Even if we use our 1 allowed 1

flip on a 100-weight

=100 and S

alidanisteter

B

3

1

0

-200. Candidate 1 still loses.
#include <bits/stdc++.h>

using namespace std;

int solve(int n, int k, vector<int>& v, vector<int>& w) ( // Write your solution here

}

int main() {

ios_base::sync_with_stdio(false); cin.tie(NULL);

int n; cin >> n;

int k; cin >> k;

vector<int> v(n);

for (int i = 0; i < n; i++) cin >> v[i];

vector<int> w(n);

for (int i = 0; i < n; i++) cin >> w[i];

auto result = solve(n, k, v, w); cout << result << endl; return 0;

}

Please give me proper code without explanation wgich

Answer 1

cpp
#include <bits/stdc++.h>
using namespace std;

int solve(int n, int k, vector<int>& v, vector<int>& w) {
    long long diff = 0;
    vector<long long> gains;

    for (int i = 0; i < n; i++) {
        if (v[i] == 1) {
            diff += w[i];
            long long gain = -2LL * w[i];  // flipping 1 -> 0
            if (gain > 0) gains.push_back(gain);
        } else {
            diff -= w[i];
            long long gain = 2LL * w[i];   // flipping 0 -> 1
            if (gain > 0) gains.push_back(gain);
        }
    }

    if (diff > 0) return 0;

    sort(gains.rbegin(), gains.rend());

    int flips = 0;
    for (long long gain : gains) {
        if (flips == k) break;
        diff += gain;
        flips++;

        if (diff > 0) return flips;
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int k;
    cin >> k;

    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    vector<int> w(n);
    for (int i = 0; i < n; i++) cin >> w[i];

    cout << solve(n, k, v, w) << endl;

    return 0;
}

You have N voters, each with a vote (0 or 1) and a...

प्रश्न

विचार

उत्तर

इस प्रश्नोत्तर को साझा करें