有基础班_day01考试

zxcvbnm

2025-07-02 16:21:07

发布于：上海

9阅读

0回复

0点赞

题目
求和
桐桐撒金币
【前缀和与差分】小码君的荣耀
投票箱
卡牌
暴躁的病人

求和

题目大意

给定 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，要求计算所有两两不同的乘积之和，即：

$S = \sum_{1 \le i < j \le n} a_i \cdot a_j$

例如，当 $a = [1, 2, 3]$ 时：

$S = 1 \cdot 2 + 1 \cdot 3 + 2 \cdot 3 = 11$

题意分析

本题目要求计算 $a_i \cdot a_j$ 的总和，满足 $1 \le i < j \le n$ 。
直接做法是使用两层循环枚举所有的 $i, j$ ，时间复杂度为 $O(n^2)$ ，当 $n$ 较大时会超时。

解题思路

我们可以利用数学变形将其优化为线性算法。

观察下面的展开形式：

$S = a_1 \cdot (a_2 + a_3 + \dots + a_n) + a_2 \cdot (a_3 + \dots + a_n) + \dots + a_{n-1} \cdot a_n$

即：

$S = \sum_{i=1}^{n-1} a_i \cdot \left( \sum_{j=i+1}^{n} a_j \right)$

因此，我们可以：

先计算前缀和数组 $pre_i = \sum_{k=1}^{i} a_k$ ；
对于每个 $a_i$ ，它的贡献是 $a_i \cdot (pre_n - pre_i)$ ；
将所有这些贡献累加得到答案。

时间复杂度解析

计算前缀和： $O(n)$ ；
枚举每个 $i$ 计算贡献： $O(n)$ ；
总时间复杂度为 $O(n)$ ；
空间复杂度为 $O(n)$ （用于存储数组和前缀和）。

代码演示

#include <iostream>
using namespace std;

int n;
long long a[100010], s;

void solve() {
    long long pre[100010] = {0};

    // 输入数组并构建前缀和
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    // 计算所有 a_i * (a_{i+1} + ... + a_n) 的和
    for (int i = 1; i <= n - 1; i++) {
        s += a[i] * (pre[n] - pre[i]);
    }

    cout << s << endl;
}

int main() {
    cin >> n;
    solve();
    return 0;
}

桐桐撒金币

题目大意

桐桐在一条公路上撒金币，每一公里都有一些金币。你需要处理 $k$ 次询问，每次询问某一段区间 $[l, r]$ 上金币的总和。

题意分析

本题本质是一个经典的区间和查询问题。

给定一个长度为 $n$ 的数组 $a$ ，和 $k$ 个区间 $[l, r]$ ，每次要回答：

$\text{区间和} = a_l + a_{l+1} + \dots + a_r$

直接每次遍历 $[l, r]$ 会超时，最坏情况下时间复杂度 $O(nk)$ 。
我们考虑使用前缀和优化查询，将每次查询降为 $O(1)$ 。

解题思路

使用前缀和数组 $pre$ ：

定义 $pre[i] = a_1 + a_2 + \dots + a_i$
则有：

$\text{区间} [l, r] \text{的和} = pre[r] - pre[l - 1]$

实现步骤：

输入数组并构建前缀和；
对每个区间查询，使用前缀和快速计算答案。

时间复杂度解析

构建前缀和数组： $O(n)$ ；
每次查询使用 $O(1)$ ，共 $k$ 次，总计 $O(k)$ ；
总时间复杂度为 $O(n + k)$ ；
空间复杂度 $O(n)$ 。

代码演示

#include<iostream>
using namespace std;

int n, k;
long long a[1000010];        // 原始数组
long long pre[1000010] = {0}; // 前缀和数组

void solve() {
    // 构建前缀和
    for (int i = 1; i <= n; i++) {
        pre[i] = a[i] + pre[i - 1];
    }

    // 回答每个询问
    for (int i = 1; i <= k; i++) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << endl;
    }
}

int main() {
    cin >> n >> k;
    
    // 读取每公里金币数量
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    solve(); // 处理询问
    return 0;
}

投票箱

题目大意

有 $N$ 个城市，总共 $B$ 个投票箱。第 $i$ 个城市有 $a_i$ 名选民。现需为每个城市分配至少一个投票箱，且每位选民必须在其城市被分配的投票箱中投票。每个投票箱可以服务一定数量的选民。

目标是通过合理分配投票箱，使得“单个投票箱服务的最大人数”尽可能小。

题意分析

这是一道最小化最大值的优化问题。

每个城市必须分至少一个箱子。
每个城市内，可以将人口均匀分配到多个箱子中，向上取整即为该城市所需投票箱数。
我们要找的是一个值 $x$ ，使得所有城市中，任意一个投票箱服务的人数不超过 $x$ ，且所需的总投票箱数量不超过 $B$ 。

解题思路

1. 二分答案

我们可以二分答案 $x$ （即单个投票箱服务的人数），判断是否存在一个分配方案使得所有选民都能完成投票且不超过 $B$ 个箱子。

2. 检查函数 check(x)

对于当前猜测的最大投票箱负载 $x$ ，我们要判断是否可以在不超过 $B$ 个投票箱的前提下覆盖所有人口：

每个城市 $i$ 至少需要 $\left\lceil \frac{a_i}{x} \right\rceil$ 个箱子；
累加所有城市所需的箱子数是否小于等于 $B$ 。

如果可以，说明 $x$ 还可以继续减小；否则 $x$ 太小了，不能满足要求。

时间复杂度解析

每组数据最多有 $5$ 组。
二分最多查找 $\log_2(5 \times 10^6) \approx 23$ 次；
每次判断 $O(N)$ ，所以总复杂度约为 $O(T \cdot N \log M)$ ，可以接受。

代码演示

#include<iostream>
#include<cmath>
using namespace std;

const int N = 5e6;  // 投票箱人数上限
int a[500010];      // 城市人口数组
int n, b;           // 城市数量、投票箱数量

// 判断当每个投票箱最多容纳 x 人时是否可行
bool check(int x) {
    int sum = 0;  // 总共需要的投票箱数
    for (int i = 1; i <= n; i++) {
        sum += ceil(a[i] / (double)x);
    }
    return sum <= b;
}

void solve() {
    int l = 1, r = N;
    int ans;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;    // 可行，尝试更小的答案
            r = mid - 1;
        } else {
            l = mid + 1;  // 不可行，需要增大x
        }
    }
    cout << ans << endl;
}

int main() {
    cin >> n >> b;
    while (n != -1 && b != -1) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        solve();  // 对当前数据组求解
        cin >> n >> b;
    }
    return 0;
}

卡牌

题目大意

有 $n$ 种卡牌，第 $i$ 种卡牌已有 $a_i$ 张。还有 $m$ 张空白卡牌可以涂写，但第 $i$ 种卡牌最多可以涂写 $b_i$ 张。现在你要尽可能多地组成“完整套牌”，即每套包含每种卡牌各一张。问：最多能组成多少套完整的卡牌？

题意分析

每组成一套完整的卡牌，需要每种卡牌各一张。若某种卡牌数量不够，可使用空白卡牌进行补充，但不能超过该种牌可手写上限 $b_i$ ，总手写卡牌数量不能超过 $m$ 。

解题思路

使用二分答案来判断最多能组成多少套完整的卡牌：

枚举可以组成的套数 $x$ ；
对于每个种类的卡牌：
- 如果已有 $a_i \ge x$ ，无需补；
- 如果 $a_i < x$ ，需要补 $x - a_i$ 张，且不能超过 $b_i$ ；
所有需要补的数量不能超过总空白卡牌数 $m$ 。

为了保证复杂度最优，采用倒序线性判断（f_20() 函数）或 二分查找（f() 函数）都可以。

时间复杂度分析

最坏情况每次判断 $O(n)$ ；
f_20() 复杂度为 $O(n \cdot A)$ ，其中 $A = m/n + \max(a_i)$ ；
f() 为 $O(n \cdot \log A)$ ，推荐在数据范围较大时使用；
对于 $n \le 2 \times 10^5$ ， $m \le 5 \times 10^6$ 是可接受的。

代码演示

#include<iostream>
#include<cmath>
#define ll long long
using namespace std;

ll n, m;
const int N = 5e6;
int a[200010]; // 原有的卡牌数量
int b[200010]; // 每种牌最大能手写的数量
int max_a = 0; // 记录最大原始卡牌数量

// 判断是否能组成 x 套卡牌
int check(int x)
{
    ll sum = 0; // 统计需要手写的卡牌总数
    for(int i = 1; i <= n; i++)
    {
        int k = x - a[i]; // 第 i 种牌需要补多少张
        if(k < 0) k = 0;
        sum += k;
        if(k > b[i]) return 0; // 超过手写上限，失败
    }
    return sum <= m; // 判断是否总手写卡牌数不超过 m
}

// 解法一：线性倒序枚举答案（暴力优化版）
void f_20()
{
    // 最多不会超过 m/n + max_a 套
    for(int i = m/n + max_a; i >= 1; i--)
    {
        if(check(i))
        {
            cout << i << endl;
            break;
        }
    }
}

// 解法二：二分答案（推荐）
void f()
{
    ll l = 1, r = m / n + max_a;
    int ans;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
        {
            ans = mid;
            l = mid + 1; // 尝试更大的解
        }
        else
        {
            r = mid - 1; // 缩小范围
        }
    }
    cout << ans << endl;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        max_a = max(max_a, a[i]);
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    //f_20(); // 使用暴力优化解法，若超时可改为 f();
    f();
    return 0;
}

暴躁的病人

题目大意

有 $N$ 个病房，坐标分别为 $x_1, x_2, \dots, x_N$ ，共 $C$ 个病人。

需要将这 $C$ 个病人安置在病房中，使得任意两个相邻病人的距离尽可能大。

求这个“最大化的最小相邻距离”。

题意分析

这是一个典型的最大化最小间距问题，类似于“放置C个元素，使它们之间的最小距离最大”。
约束：
- 每个病人占一个病房；
- 病房的坐标可能无序，需要先排序；
- 目标是找到一个最小距离 $d$ ，使得能把 $C$ 个病人安排进病房，使得任意两人之间距离至少 $d$ 。

解题思路

1. 先排序

将病房坐标 $x_i$ 按升序排序。

2. 二分距离

用二分法枚举最小距离 $mid$ ：

判定函数 check(mid) 判断能否安排 $C$ 个病人在病房中，使得任意两人距离至少为 $mid$ 。
方法：
- 第一个病人安排在第一个病房（下标1）；
- 遍历后续病房，若当前病房和上一个安排病人的病房距离 $\ge mid$ ，则安排一个病人；
- 统计安排了多少病人，若 $\ge C$ ，则说明可以用 $mid$ 距离安排，返回真。

3. 二分调整

初始左右边界： $l=0$ ， $r= \max(x) - \min(x)$ （最大坐标差）。
若 check(mid) 成功，更新答案，尝试更大距离 $l=mid+1$ ；
否则缩小距离 $r=mid-1$ 。

代码演示

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000010;
int n, c;
int a[MAXN];

// 判断是否能以距离 x 安排 c 个病人
bool check(int x) {
    int count = 1;      // 第一个病人放在第一个病房
    int last_pos = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] - last_pos >= x) {
            count++;
            last_pos = a[i];
            if (count >= c) return true;
        }
    }
    return false;
}

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

    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a, a + n);

    int l = 0, r = a[n-1] - a[0];
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;      // mid 可行，尝试更大
            l = mid + 1;
        } else {
            r = mid - 1;    // mid 不可行，减小距离
        }
    }

    cout << ans << "\n";

    return 0;
}