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