题意简述

小程今年想去公园 $n$ 次。

门票有两种：

• 单次票：每次花费 $a$ 元；
• 年票：花费 $b$ 元，买一次后今年可以无限次进入。

要求计算最少花费。

---

思路分析

如果全部购买单次票，那么总花费为：

$$n \times a$$

如果购买年票，那么总花费为：

$$b$$

所以答案就是：

$$\min(n \times a,\ b)$$

但是本题数据范围较大：

$$0 \le n,a,b \le 10^{18}$$

如果直接计算 $n \times a$，最大可能达到：

$$10^{18} \times 10^{18} = 10^{36}$$

会超过 long long 的范围。

因此可以不直接计算 $n \times a$，而是通过比较单次票价格 $a$ 和年票平均到每次的价格来判断。

---

判断方法

当 $n=0$ 时，小程不去公园，答案一定是 $0$。

当 $n>0$ 时，比较 $b$ 和 $n \times a$。

为了避免乘法溢出，可以用除法比较：

情况一：$b$ 能被 $n$ 整除

如果：

$$\frac{b}{n} > a$$

说明年票平均每次比单次票还贵，选择单次票。

否则选择年票。

情况二：$b$ 不能被 $n$ 整除

此时要看：

$$\left\lfloor \frac{b}{n} \right\rfloor$$

如果：

$$\left\lfloor \frac{b}{n} \right\rfloor \ge a$$

说明 $b > n \times a$，选择单次票。

否则选择年票。

---

代码

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

int main(){
    long long a, b, n;
    cin >> n >> a >> b;

    // 不去公园，不需要买票
    if(n == 0){
        cout << 0;
        return 0;
    }

    // 如果 b 能被 n 整除
    if(b % n == 0){
        if(b / n > a)
            cout << a * n;
        else
            cout << b;
    }
    // 如果 b 不能被 n 整除
    else{
        if(b / n >= a)
            cout << n * a;
        else
            cout << b;
    }

    return 0;
}

题意分析

小程初始有 $x$ 积分，面前有 $n$ 台抽奖机。

第 $i$ 台抽奖机：

• 需要 $a_i$ 积分才能游玩；
• 游玩后获得 $b_i$ 积分。

小程从第 $1$ 台开始按顺序游玩，过程中可能会停止：

1. 如果游玩某台抽奖机后积分大于等于 $y$，则停止；
2. 如果在游玩某台抽奖机前，当前积分小于 $a_i$，则无法游玩，停止；
3. 如果所有抽奖机都游玩完，也停止。

要求输出停止时小程拥有的积分数量。

---

思路分析

按照题目要求直接模拟即可。

设当前积分为 $x$。

对于第 $i$ 台抽奖机：

首先判断当前积分是否足够：

$$x < a_i$$

如果不够，则小程无法继续游玩，直接输出当前积分 $x$。

否则，小程可以游玩该抽奖机，游玩后的积分变为：

$$x = x - a_i + b_i$$

然后判断是否达到目标积分：

$$x \ge y$$

如果达到，则停止并输出当前积分。

如果没有达到，则继续游玩下一台抽奖机。

如果所有抽奖机都处理完，输出最终积分即可。

---

代码实现

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

long long a[100010], b[100010];

int main(){
    long long n, x, y;
    cin >> n >> x >> y;

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

    for(int i = 1; i <= n; i++){
        // 如果当前积分不足以游玩第 i 台抽奖机，则停止
        if(x < a[i]){
            cout << x;
            return 0;
        }

        // 游玩第 i 台抽奖机
        x = x - a[i] + b[i];

        // 如果积分达到 y，则停止
        if(x >= y){
            cout << x;
            return 0;
        }
    }

    // 所有抽奖机都游玩完
    cout << x;

    return 0;
}

题意简述

给定一副从顶到底排列好的 $n$ 张牌。

现在给定参数 $k$，先将牌分成两堆：

• 牌堆 A：原来的第 $1$ 张到第 $k$ 张；
• 牌堆 B：原来的第 $k+1$ 张到第 $n$ 张。

然后从牌堆 A 开始，两个牌堆轮流取出顶部的一张牌，放入新牌堆底部。

如果其中一堆牌先被取完，则把另一堆剩余的牌按原顺序放到新牌堆底部。

要求输出洗牌后的结果。

---

思路分析

按照题目要求直接模拟即可。

可以先把原数组分成两个数组：

• b 数组存储前 $k$ 张牌，也就是牌堆 A；
• c 数组存储后面的 $n-k$ 张牌，也就是牌堆 B。

然后从两个数组的开头开始轮流取牌：

1. 先取牌堆 A 的一张；
2. 再取牌堆 B 的一张；
3. 重复上述过程。

直到其中一个牌堆已经没有牌。

最后把仍有剩余的牌堆继续输出即可。

---

举例说明

以样例 1 为例：

n = 6, k = 2
原牌堆：1 2 3 4 5 6

分成两堆：

A：1 2
B：3 4 5 6

轮流取牌：

1 3 2 4

此时 A 已经取完，B 还剩：

5 6

所以最终结果为：

1 3 2 4 5 6

---

代码实现

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

long long n, k;
long long a[2005], b[2005], c[2005];

int main(){
    cin >> n >> k;

    int s1 = 0, s2 = 0;

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

        if(i <= k){
            b[++s1] = a[i];//相当于 s1++; b[s1]=a[i]
        }else{
            c[++s2] = a[i];
        }
    }

    int i = 1, j = 1;//i 和j指向 b 和 c 当前正在取得的元素下标

    // 两堆都还有牌时，轮流取
    while(i <= s1 && j <= s2){
        cout << b[i++] << " ";   //cout<<b[i++] 相当于  cout<<b[i]; i++;
        cout << c[j++] << " ";
    }

    // 如果牌堆 A 还有剩余
    while(i <= s1){
        cout << b[i++] << " ";
    }

    // 如果牌堆 B 还有剩余
    while(j <= s2){
        cout << c[j++] << " ";
    }

    return 0;
}

题意简述

一条地铁线路共有 $n$ 个车站，被划分成 $k$ 个收费区。

给出 $k+1$ 个分界点：

$$1=p_0<p_1<p_2<\cdots<p_k=n+1$$

第 $t$ 个收费区包含的车站范围为：

$$[p_{t-1},p_t-1]$$

对于每次询问 $(i,j)$，要求计算从车站 $i$ 到车站 $j$ 的车费。

计费规则如下：

1. 如果起点和终点相同，收费 $1$ 元；
2. 如果起点和终点在同一收费区内，且不是同一站，收费 $2$ 元；
3. 否则，若起点和终点之间完整包含了 $m$ 个收费区，收费：

$$2+m$$

---

思路分析

由于 $n$ 最大可以达到 $10^9$，所以不能按车站开数组。

但是题目中收费区数量满足：

$$k\le 1000$$

因此可以对每一次询问，直接枚举所有收费区，判断：

1. 起点所在的收费区；
2. 终点所在的收费区；
3. 有多少个收费区被询问区间完整包含。

对于一次询问 $(i,j)$，因为从 $i$ 到 $j$ 和从 $j$ 到 $i$ 的车费相同，所以先令：

$$a=\min(i,j),\quad b=\max(i,j)$$

这样只需要考虑区间 $[a,b]$。

---

判断方法

对于第 $t$ 个收费区，它的左右端点为：

$$l=p_{t-1},\quad r=p_t-1$$

如果满足：

$$l\le a\le r$$

说明起点 $a$ 在第 $t$ 个收费区。

如果满足：

$$l\le b\le r$$

说明终点 $b$ 在第 $t$ 个收费区。

如果满足：

$$a\le l \quad \text{且} \quad r\le b$$

说明整个收费区 $[l,r]$ 被乘车区间 $[a,b]$ 完整包含，需要计入 $m$。

---

代码实现

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

long long p[1005];

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

    long long n;
    int k;
    cin >> n >> k;

    for (int i = 0; i <= k; i++) {
        cin >> p[i];
    }

    int q;
    cin >> q;

    while (q--) {
        long long i, j;
        cin >> i >> j;

        long long a = min(i, j);
        long long b = max(i, j);

        // 同一车站进出
        if (a == b) {
            cout << 1 << '\n';
            continue;
        }

        int zoneA = -1, zoneB = -1;
        int cnt = 0;

        // 枚举所有收费区
        for (int t = 1; t <= k; t++) {
            long long l = p[t - 1];
            long long r = p[t] - 1;

            // 判断 a 在哪个收费区
            if (l <= a && a <= r) {
                zoneA = t;
            }

            // 判断 b 在哪个收费区
            if (l <= b && b <= r) {
                zoneB = t;
            }

            // 判断当前收费区是否被 [a,b] 完整包含
            if (a <= l && r <= b) {
                cnt++;
            }
        }

        // 同一收费区内不同车站
        if (zoneA == zoneB) {
            cout << 2 << '\n';
        } else {
            cout << 2 + cnt << '\n';
        }
    }

    return 0;
}