题面描述 给定区域覆盖需求面积$areaRequirement$（单位：m²）和总预算$budget$（单位：元），以及 $n$ 个可选接入点。第$i$个接入点的信号覆盖范围为$coverage_i$（m²），安装成本为 $cost_i$（元）。在不超过总预算的前提下，选择若干接入点，使得覆盖总面积至少为 $areaRequirement$。如果有多种选择方式都满足覆盖需求，则选取总成本最小；若成本相同，则取覆盖总面积最大的方案。如果无法满足需求，则输出$0$。

思路 这是一个典型的「0-1 背包」变形问题：

• “重量” 对应 每个接入点的成本$cost_i$
• “价值” 对应 每个接入点的覆盖面积$coverage_i$
• 背包容量 即 总预算$budget$
• 目标是保证价值总和$ge areaRequirement$，同时最小化所用“重量”，并在相同重量下最大化价值。

常规做法：

1. 使用一维数组 dp[j] 表示在预算不超过$j$时，所能获得的最大覆盖面积。

2. 初始化 dp[0…budget] = 0。

3. 对于每个接入点，倒序遍历预算$j$从$budget$到$cost_i$，更新：

   $$dp[j]=max(dp[j],dp[j - cost_i] + coverage_i)$$

4. 最后线性扫描 dp[j]，找到最小的$j$满足$dp[j] ge areaRequirement$，并输出该$j$ 及对应的$dp[j]$。

时间优化

• $budget$ 最大可达$10000$，$n$最大$10000$，直接$O(n \times budget)$ 最坏 $10^8$ 次，Python 可能超时。
• 由于所有成本均为$10$的倍数，可将成本先除以$10$，使新背包容量 $budget' = budget / 10<=1000$，将复杂度降为$O(n \times budget')<=10^7$，在大多数语言中均可接受。

问题本质分析 本质上是「0-1 背包」问题的双目标优化：

1. 主目标：覆盖面积$ge areaRequirement$
2. 次目标：总成本最小；若成本相同，则覆盖面积最大

通过一维动态规划记录在不同预算下的最大覆盖面积，即可同时兼顾这两点：最小预算优先被遍历到，覆盖面积又被最大化维护。

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int areaRequirement, budget, n;
    cin >> areaRequirement >> budget >> n;

    // 将预算缩放：除以10
    int B = budget / 10;
    vector<int> dp(B + 1, 0);

    for(int i = 0; i < n; i++){
        int coverage, cost;
        cin >> coverage >> cost;
        int c = cost / 10;  // 缩放后的成本
        // 倒序遍历保证每个物品只选一次
        for(int j = B; j >= c; j--){
            dp[j] = max(dp[j], dp[j - c] + coverage);
        }
    }

    // 在缩放后容量范围内查找最优解
    for(int j = 0; j <= B; j++){
        if(dp[j] >= areaRequirement){
            // 输出时记得将成本乘回10
            cout << j * 10 << " " << dp[j] << "\n";
            return 0;
        }
    }
    // 无解
    cout << 0 << "\n";
    return 0;
}

Python

import sys

# 读取输入
a, b, n = map(int, sys.stdin.readline().split())
# 将预算缩放：除以10
B = b // 10
# dp[j] 表示预算不超过 j*10 时最大覆盖面积
dp = [0] * (B + 1)

for _ in range(n):
    coverage, cost = map(int, sys.stdin.readline().split())
    c = cost // 10  # 缩放后的成本
    # 倒序遍历，保证0-1性质
    for j in range(B, c - 1, -1):
        dp[j] = max(dp[j], dp[j - c] + coverage)

# 查找最小预算满足覆盖需求
for j in range(B + 1):
    if dp[j] >= a:
        # 输出时将成本乘回10
        print(j * 10, dp[j])
        break
else:
    # 无解
    print(0)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int areaRequirement = Integer.parseInt(st.nextToken());
        int budget = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        // 将预算缩放：除以10
        int B = budget / 10;
        int[] dp = new int[B + 1];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(in.readLine());
            int coverage = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            int c = cost / 10;  // 缩放后的成本

            // 倒序遍历，确保0-1背包
            for (int j = B; j >= c; j--) {
                dp[j] = Math.max(dp[j], dp[j - c] + coverage);
            }
        }

        // 查找最小预算满足覆盖需求
        for (int j = 0; j <= B; j++) {
            if (dp[j] >= areaRequirement) {
                // 输出时将成本乘回10
                System.out.println((j * 10) + " " + dp[j]);
                return;
            }
        }
        // 无解
        System.out.println(0);
    }
}

题目内容

你正在设计一个大型无线网络覆盖计划，目标是通过布置多个无线接入点来覆盖一个区域。每个接入点都有不同的信号覆盖范围，安装成本。在预算有限的情况下，保证网络覆盖需求满足，并且总成本不超过预算。

约束条件：

信号覆盖范围：每个接入点能够覆盖一定的区域，区域面积单位为 $m^2$ 。

安装成本：每个接入点有一定的安装成本，单位为元，总成本不应超过预算。

区域需求：你知道整个区域的总覆盖面积需求，单位为 $m^2$。

输入描述

1、第一行包含三个数字

$areaRequirement$：所需的区域覆盖面积(单位：$m^20<areaRequirement<=100000$)。

$budget$：总预算（单位：元 $0<budget<=10000$ $budget$ 为 $10$ 的整数倍）。

$n$ ：接入点的数量 $(0<n<= 10000)$ 。

2、接下来的 $n$ 行每行包含两个数字，分别是：

$coverage$ ：接入点的信号覆盖范围（单位：$m^20<coverage<=100000$）。

$cost$ ：接入点的安装成本(单位：元 $0<cost=100000$ $cost$ 为 $10$ 的整数倍)。

输出描述

1、输出在给定成本内能满足区域覆盖需求的最小预算以及此时的覆盖面积，如果有多个解预算都能满足覆盖范围要求，输出预算最小时最大的覆盖面积

2、如果给出的站点无法满足要求则输出 $0$ $0$

样例1

输入

2000 500 3
1000 200
1500 250
800 180

输出

430 2300

说明

1、第一行表示：目标是需要一个信号覆盖范围至少为 $2000$ $m^2$的区域，总预算为 $500$ 元，共有 $3$ 个接入点可供选择

2、接下来 $3$ 行表示：

接入点 $1$：覆盖范围 $1000$ $m^2$，成本 $200$ 元

接入点 $2$：覆盖范围 $1500$ $m^2$，成本 $250$ 元

接入点 $3$：覆盖范围 $800$ $m^2$，成本 $180$ 元

可选接入点 $2$ 和接入点 $3$ 成本最低 $430$ 元能满足覆盖范围 $2300$$m^2$

样例2

输入

3000 500 3
1000 200
1500 250
800 180

输出

0 0

说明

1、第一行表示：目标是需要一个信号覆盖范围至少为 $3000$ $m^2$的区域，总预算为 $500$ 元，共有 $3$ 个接入点可供选择

2、接下来 $3$ 行表示：

接入点 $1$：覆盖范围 $1000$ $m^2$，成本 $200$ 元

接入点 $2$：覆盖范围 $1500$ $m^2$，成本 $250$ 元

接入点 $3$：覆盖范围 $800$ $m^2$，成本 $180$ 元

无论选择哪些接入点，都无法满足 在不超过预算 $500$ 的情况下满足 $3000$ $m^2$的区域覆盖需求

所以输出 $0$ $0$