2 条题解

  • 0
    @ 2025-3-10 22:09:07

    问题分析

    本题要求找到最少的区域数,使得农夫 dash 获得的总票数超过 Code 的票数。 每个区域有:

    • 忠于 Code 的山羊aia_i
    • 忠于 dash 的绵羊bib_i

    规则:

    • 若 不分发干草:
      • 山羊 aia_i 投票给 Code
      • 绵羊 bib_i 不投票
    • 若 分发干草:
      • 该区域的 所有 山羊和绵羊 都投票给 dash

    解法思路

    我们需要找出最少的区域数,使得 dash 获得的选票数超过 Code

    1. 计算初始差距

    初始时,dash 没有任何投票,而 Code 获得了所有山羊的票数:

    X=i=1NaiX = -\sum_{i=1}^{N} a_i

    即 dash 落后于 Code 的选票数

    2. 计算每个区域的增益

    对于每个区域,如果选择分发干草,那么:

    • 山羊 aia_i 从 Code 转向 dash,收益是 +ai+a_i
    • 额外增加绵羊 bib_i 的支持,收益是 +bi+b_i

    因此,总收益:

    贡献值=2ai+bi\text{贡献值} = 2a_i + b_i

    我们可以将所有区域的贡献值存入数组 x[]

    3. 选择收益最高的区域

    为了最小化分发干草的数量,我们要 优先选择贡献值最高的区域。 因此,我们将 x[] 从大到小排序,然后依次累加贡献值,直到 dash 反超 Code。

    算法步骤

    1. 计算初始选票差距 XX
      • Code 初始票数:所有山羊的数量总和 ai\sum a_i
      • dash 初始票数:0
      • X = -sum(A) 表示 dash 的劣势
    2. 计算每个区域的贡献值:
      • x[i] = 2 * a[i] + b[i]
    3. 排序贡献值数组 x[](降序)
    4. 贪心策略:
      • 从贡献值最高的区域开始选择,累加到 X 变为正数
      • 统计所需的最小区域数
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    using ll = int64_t;
    
    int main(){
        ll N;
        cin >> N;
        ll X = 0;
        vector<ll> x(N);
        for(ll i = 0; i < N; i++){
            ll A, B;
            cin >> A >> B;
            X -= A;
            x[i] = A + A + B;
        }
        sort(x.begin(), x.end());
        ll ans = 0;
        while(X <= 0){
            X += x.back();
            x.pop_back();
            ans++;
        }
        cout << ans << endl;
    }
    
    import java.io.*;
    import java.util.*;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter out = new PrintWriter(System.out);
    
            int N = Integer.parseInt(br.readLine());
            long X = 0;
            long[] x = new long[N];
    
            for (int i = 0; i < N; i++) {
                String[] input = br.readLine().split(" ");
                long A = Long.parseLong(input[0]);
                long B = Long.parseLong(input[1]);
                X -= A;  // 初始情况下,dash 落后 Code a_i 票
                x[i] = 2 * A + B;  // 计算每个区域的贡献值
            }
    
            Arrays.sort(x); // 默认升序,我们需要降序
            int ans = 0;
            while (X <= 0) {
                X += x[N - 1 - ans]; // 从贡献值最大的开始选
                ans++;
            }
    
            out.println(ans);
            out.flush();
        }
    }
    
    import sys
    
    def solve():
        N = int(sys.stdin.readline().strip())
        
        X = 0
        x = []
        
        for _ in range(N):
            A, B = map(int, sys.stdin.readline().split())
            X -= A  # 初始情况下,dash 落后 Code a_i 票
            x.append(2 * A + B)  # 计算每个区域的贡献值
        
        x.sort(reverse=True)  # 按贡献值从大到小排序
    
        ans = 0
        while X <= 0:
            X += x[ans]  # 选取贡献值最高的区域
            ans += 1
    
        print(ans)
    
    if __name__ == "__main__":
        solve()
    

    信息

    ID
    296
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    69
    已通过
    16
    上传者