百度之星2024 初赛第一场 补给

题干描述

参考自马蹄集OJ，原文链接1

可怕的战争发生了，小度作为后勤保障工作人员，也要为了保卫国家而努力。
现在有 𝑁(1≤𝑁≤103)个堡垒需要补给，然而总的预算 𝐵(1≤𝐵≤10^9)是有限的。
现在已知第 𝑖 个堡垒需要价值 𝑃(𝑖)的补给，并且需要 𝑆(𝑖)的运费。- 鉴于小度与供应商之间长期稳定的合作关系，供应商慷慨地提供了一次特别的采购优惠。 - 具体而言，小度可以选择对某次补给进行半价采购。- 这意味着，如果小度决定在向第 𝑖 个堡垒提供补给时利用这一优惠，- 那么此次补给的采购及运输总费用将减少至 ⌊𝑃(𝑖)/2⌋+𝑆(𝑖)，其中优惠价格按照向下取整的原则计算。- 对于其他堡垒 j，补给的采购和运输费用则保持不变，即 𝑃(𝑗)+𝑆(𝑗)。请计算小度的最多能给多少堡垒提供补给？

格式
输入格式：

第1行2个整数：𝑁和 𝐵 。(1≤𝑁≤103,1≤𝐵≤10^9)； 第2到 𝑁+1行：第 𝑖+1
行包含两个空格分隔的整数，𝑃(𝑖)和𝑆(𝑖)。(0≤P(i),S(i)≤10^9)。

输出格式：

1 行 1 个整数表示能提供补给的最大数。

样例 1
输入：

5 29
6 3
2 8
10 2
1 2
12 5

输出：

4

**

问题分析：

1.注意本题要求的是尽可能多的堡垒，那么我们的目标就是尽量优先那些花费少的堡垒。
2.读题的时候要注意，每个堡垒花费来自两个方面，一个是补给本身𝑃(𝑗)，一个是运费𝑆(𝑗))，所以考虑的时候，应该是二者的和𝑃(𝑗)+𝑆(𝑗)。
3.为了尽可能多的补给堡垒，那么应该对运费和补给费用的和（𝑃(𝑗)+𝑆(𝑗)）从小到大进行排序。
4.考虑优惠政策，由于只能用一次，为了优惠的最多，是不是考虑给贵的堡垒？但是如果直接给最贵的可能导致钱变少了，因此是不是应该先从少的开始，直到不够了，再试试能不能通过打折为更多的堡垒供给。
5.因此本地就是排序+贪心（贪心策略：每次选择总费用最少的堡垒）。

C++代码

参考文章2

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>using namespace std;typedef long long ll;const int N=1010;struct node
{ll p;ll s;ll sum;
}a[N];bool cmp(node x,node y)
{return x.sum<y.sum;
}int ans;int main()
{int n,B; cin>>n>>B;for(int i=1;i<=n;i++) cin>>a[i].p>>a[i].s;for(int i=1;i<=n;i++) a[i].sum=a[i].p+a[i].s;sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){if(B>=a[i].sum){B-=a[i].sum;ans++;}else{if(B>=floor(a[i].p/2)+a[i].s){ans++;break;}}}cout<<ans<<endl;return 0;
}

Java代码：

import java.util.Scanner;
import java.util.*;class Main {static class Fort {long p;long s;long sum;Fort(long p, long s) {this.p = p;this.s = s;this.sum = p + s;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();long B = scanner.nextLong();Fort[] forts = new Fort[N];for (int i = 0; i < N; i++) {long p = scanner.nextLong();long s = scanner.nextLong();forts[i] = new Fort(p, s);}Arrays.sort(forts, Comparator.comparingLong(f -> f.sum));int maxCount = 0;for (int i = 0; i < N; i++) {long discountedCost = forts[i].p / 2 + forts[i].s;if (discountedCost > B) {continue;}long remaining = B - discountedCost;int count = 1;for (int j = 0; j < N; j++) {if (j == i) {continue;}if (remaining >= forts[j].sum) {remaining -= forts[j].sum;count++;} else {break;}}if (count > maxCount) {maxCount = count;}}System.out.println(maxCount);}
}

Python代码

def max_forts():import sysinput = sys.stdin.read().split()idx = 0N = int(input[idx])idx += 1B = int(input[idx])idx += 1forts = []for _ in range(N):p = int(input[idx])idx += 1s = int(input[idx])idx += 1forts.append((p, s, p + s))forts.sort(key=lambda x: x[2])max_count = 0for i in range(N):discounted_cost = forts[i][0] // 2 + forts[i][1]if discounted_cost > B:continueremaining = B - discounted_costcount = 1for j in range(N):if j == i:continueif remaining >= forts[j][2]:remaining -= forts[j][2]count += 1else:breakif count > max_count:max_count = countprint(max_count)max_forts()

补充说明：

大家首先一定要学会基础的内容哦，例如需要自行编写代码，获得用例的输入，本题的C++代码为例：

int n,B; cin>>n>>B;
for(int i=1;i<=n;i++) cin>>a[i].p>>a[i].s;
for(int i=1;i<=n;i++) a[i].sum=a[i].p+a[i].s;