logoChat01.ai

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

Créé le : 26 avril 2026

Répondu en utilisant GPT-5.5 Thinking par Chat01

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

  1. Since 2035 winning. Candidate 1 is already

Case 2

Input:

4

2

0

0

0

1

10

20

5

5

Output

1

14

Explanation:

5

1

  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

0

100

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

0

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

Réflexion

Parsing and optimizing vote flip strategy

We need to determine the minimum number of flips required to make candidate 1 win. We only flip zero votes to one, as flipping one to zero would harm the outcome. I’ll sort the zero votes by weight and flip the largest until the difference becomes positive or we hit the flip limit.

Thought for 7s

Réponse

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;
}

Partager cette Q&R