问题分析 本题要求找到最少的区域数，使得农夫 dash 获得的总票数超过 Code 的票数。 每个区域有： - 忠于 Code 的山羊：$a_i$ 只 - 忠于 dash 的绵羊：$b_i$ 只 规则： - 若 不分发干草： - 山羊 $a_i$ 投票给 Code - 绵羊 $b_i$ 不投票 - 若 分发干草： - 该区域的 所有 山羊和绵羊 都投票给 dash 解法思路 我们需要找出最少的区域数，使得 dash 获得的选票数超过 Code。 1. 计算初始差距 初始时，dash 没有任何投票，而 Code 获得了所有山羊的票数： $$ X = -\sum_{i=1}^{N} a_i $$ 即 dash 落后于 Code 的选票数。 2. 计算每个区域的增益 对于每个区域，如果选择分发干草，那么： - 山羊 $a_i$ 从 Code 转向 dash，收益是 $+a_i$。 - 额外增加绵羊 $b_i$ 的支持，收益是 $+b_i$。 因此，总收益： $$ \text{贡献值} = 2a_i + b_i $$ 我们可以将所有区域的贡献值存入数组 x[]。 3. 选择收益最高的区域 为了最小化分发干草的数量，我们要 优先选择贡献值最高的区域。 因此，我们将 x[] 从大到小排序，然后依次累加贡献值，直到 dash 反超 Code。 算法步骤 1. 计算初始选票差距 $X$： - Code 初始票数：所有山羊的数量总和 $\sum a_i$ - dash 初始票数：0 - X = -sum(A) 表示 dash 的劣势 2. 计算每个区域的贡献值： - x[i] = 2 a[i] + b[i] 3. 排序贡献值数组 x[]（降序） 4. 贪心策略： - 从贡献值最高的区域开始选择，累加到 X 变为正数 - 统计所需的最小区域数 ```cpp #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; } ``` ```java 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(); } } ``` ```python 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() ```

本题使用贪心即可，code开始会有n个区域内的ai的山羊支持他，而dash开始是没有羊支持的，但是他分一堆干草可以获得该区域山羊的支持，也可以获得绵羊的支持，该区域的山羊从支持code变为支持dash，所以他获得的贡献就是2ai+bi ``` #include<cstdio> #include<iostream> #include<vector> #include<map> #include<cstring> #include<array> #include<queue> #include<algorithm> #include<set> #include<cmath> using namespace std; using i64=long long; //using i128=__int128; const i64 INF=1e18; const int mod=998244353; //const int N=1e9+7; void solve(){ int n; cin>>n; vector<int>a(n+1),b(n+1); i64 sum=0; for(int i=1;i<=n;i++)cin>>a[i]>>b[i],sum+=a[i]; vector<i64>ans; for(int i=1;i<=n;i++)ans.push_back(2ll*a[i]+b[i]); sort(ans.begin(),ans.end(),greater<i64>()); i64 cnt=0; i64 s=0; for(int i=0;i<n;i++){ s+=ans[i]; cnt++; if(s>sum)break; } cout<<cnt<<'\n'; } int main(){ int _=1; //cin>>_; while(_--)solve(); return 0; } ```