題干描述

參考自馬蹄集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;