笔试时间：2025年9月7日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

小明接触到一款城市建设游戏，需要建造很多设施，其中一些设施可以提供电力，另一些会消耗电力，每种设施只能建造至多一个，且建造设施需要花费一定资金。若某一时刻剩余电量（所有发电设施产生的电力减去其他设施消耗的电力）恰好为1，就能获得《高子电量》稀有成就。计算在花费最少资金的情况下达成这一成就的方案。

输入描述

输出描述

如果无法做到剩余电量为1，则输出-1；如果可以，则输出所需花费的最小资金

样例输入

4

8 1

-4 2

-2 3

-1 4

样例输出

10

参考题解

解题思路：

这是一个背包问题的变种。使用偏移量处理负下标，定义dp[i]表示总电力为(i-shift)时的最小花费。对于正电力设施从大到小更新（01背包标准做法），对于负电力设施从小到大更新。

C++：

#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 1e9 + 7;

struct Facility {
    int power;
    int cost;
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n;
    std::cin >> n;
    std::vector<Facility> facilities(n);
    int total_positive_power = 0;
    int total_negative_power = 0;
    
    for (int i = 0; i < n; ++i) {
        std::cin >> facilities[i].power >> facilities[i].cost;
        if (facilities[i].power > 0) {
            total_positive_power += facilities[i].power;
        } else {
            total_negative_power += facilities[i].power;
        }
    }
    
    int shift = -total_negative_power;
    int dp_size = total_positive_power - total_negative_power + 1;
    std::vector<int> dp(dp_size, INF);
    dp[shift] = 0;
    
    for (const auto& f : facilities) {
        if (f.power >= 0) {
            for (int j = dp_size - 1; j >= f.power; --j) {
                if (dp[j - f.power] != INF) {
                    dp[j] = std::min(dp[j], dp[j - f.power] + f.cost);
                }
            }
        } else {
            for (int j = 0; j < dp_size + f.power; ++j) {
                if (dp[j - f.power] != INF) {
                    dp[j] = std::min(dp[j], dp[j - f.power] + f.cost);
                }
            }
        }
    }
    
    int target_index = 1 + shift;
    if (target_index >= 0 && target_index < dp_size && dp[target_index] != INF) {
        std::cout << dp[target_index] << std::endl;
    } else {
        std::cout << -1 << std::endl;
    }
    
    return 0;
}

Java：

import java.util.*;

public class Solution {
    static final int INF = 1000000007;
    
    static class Facility {
        int power;
        int cost;
        
        Facility(int power, int cost) {
            this.power = power;
            this.cost = cost;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Facility> facilities = new ArrayList<>();
        int totalPositivePower = 0;
        int totalNegativePower = 0;
        
        for (int i = 0; i < n; i++) {
            int power = sc.nextInt();
            int cost = sc.nextInt();
            facilities.add(new Facility(power, cost));
            if (power > 0) {
                totalPositivePower += power;
            } else {
                totalNegativePower += power;
            }
        }
        
        int shift = -totalNegativePower;
        int dpSize = totalPositivePower - totalNegativePower + 1;
        int[] dp = new int[dpSize];
        Arrays.fill(dp, INF);
        dp[shift] = 0;
        
        for (Facility f : facilities) {
            if (f.power >= 0) {
                for (int j = dpSize - 1; j >= f.power; j--) {
                    if (dp[j - f.power] != INF) {
                        dp[j] = Math.min(dp[j], dp[j - f.power] + f.cost);
                    }
                }
            } else {
                for (int j = 0; j < dpSize + f.power; j++) {
                    if (dp[j - f.power] != INF) {
                        dp[j] = Math.min(dp[j], dp[j - f.power] + f.cost);
                    }
                }
            }
        }
        
        int targetIndex = 1 + shift;
        if (targetIndex >= 0 && targetIndex < dpSize && dp[targetIndex] != INF) {
            System.out.println(dp[targetIndex]);
        } else {
            System.out.println(-1);
        }
    }
}

Python：

INF = 10**9 + 7

n = int(input())
facilities = []
total_positive_power = 0
total_negative_power = 0

for _ in range(n):
    power, cost = map(int, input().split())
    facilities.append((power, cost))
    if power > 0:
        total_positive_power += power
    else:
        total_negative_power += power

shift = -total_negative_power
dp_size = total_positive_power - total_negative_power + 1
dp = [INF] * dp_size
dp[shift] = 0

for power, cost in facilities:
    if