8.27测试总结 - 洛谷保存站

## B3687 [语言月赛202212] 数字口袋
### 题目大意
  小 $A$ 有一个口袋，里面可以装整数。他从 $1$ 开始，按从小到大的顺序，依次将每个整数装入口袋。

但是口袋是有限的，大小为 $n$，这就是说，口袋里所有的数字的和不能够超过 $n$。
  
------------
### 解法
从 $1$ 开始枚举每个数字 $i$ ，如果可以装入口袋，则输出这个数字，然后将口袋的大小减去 $i$ ； 如果不能装入口袋，则结束循环。
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {    
    int n;   
    cin >> n; 
    for (int i = 1; ; i++) {
        // 如果当前口袋剩余容量小于要放入的数字i
        if (n < i) {
            break;   // 跳出循环，停止放入数字
        }
        cout << i << "\n";  // 输出当前可以放入的数字i
        n = n - i;   // 从口袋容量中减去已放入的数字i
    }
    
    return 0;    
}
```
## P1897 电梯里的尴尬
### 题意
嗯对大概就是题目里的这一段：
> 电梯最开始在 0 层，并且最后必须再回到 0 层才算一趟任务结束。假设在开始的时候已知电梯内的每个人要去的楼层，你能计算出完成本趟任务需要的总时间吗?

(把```吗？```去掉谢谢)

------------------
### 解法
可以把总时间分成四个部分组成：从$0$层到最高楼层的上行时间、从最高楼层返回$0$层的下行时间、所有停靠楼层的开门时间、以及所有乘客的下车时间。

首先读取乘客人数及其目标楼层数据，对楼层进行排序以便确定运行路线。然后计算上行时间（最高楼层$×6$ 秒）和下行时间（最高楼层$×4$ 秒）。接着统计唯一停靠楼层数量，计算开门时间（停靠次数$×5$ 秒）。最后加上所有乘客的下车时间（人数$×1$ 秒），求和即得总耗时。

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

int main() {
    int n;          // 乘客人数
    cin >> n;
    
    int a[n];       // 存储目标楼层
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    sort(a, a + n); // 排序楼层确定路线
    
    int top = a[n - 1];         // 最高楼层
    int time = top * 10;        // 上行6秒+下行4秒=10秒每层
    
    int stops = 1;              // 至少有一个停靠点
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) {
            stops++;            // 统计唯一停靠楼层
        }
    }
    time += stops * 5;          // 每个停靠点开门5秒
    
    time += n;                  // 每人下车1秒
    
    cout << time << endl;
    
    return 0;
}
```
## P3662 [USACO17FEB] Why Did the Cow Cross the Road II S
### 题意
有一条路，上面有 $N$ 个信号灯，编号从 $1$ 到 $N$。有些灯坏了，要修一些灯，让某一段连续的$K$个灯都是好的。问最少要修几个灯
### 解法
想要一段连续的 $K$ 个灯都亮，那么这段区间里的坏灯都要修好。所以我们只需要找出所有长度为 $K$ 的区间，看看哪个区间里的坏灯最少，这个最少的坏灯数就是答案。

前缀和启动！！
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
bool bad[MAXN];
int pre[MAXN];
int main() {
    int n, k, b;
    cin >> n >> k >> b;
    for (int i = 0; i < b; i++) {
        int x;
        cin >> x;
        bad[x] = true;         // 记录坏灯编号
    }       // 前缀和数组
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i-1] + bad[i];  // 计算到第i个位置的总坏灯数
    }
    
    int ans = n;               // 初始化答案为最大值
    for (int i = k; i <= n; i++) {
        int cnt = pre[i] - pre[i - k];  // 计算区间[i-k+1, i]内的坏灯数
        if (cnt < ans) ans = cnt;       // 更新最小坏灯数
    }
    
    cout << ans;
    return 0;
}
```
## B3784 [语言月赛202306] 演唱会
### 题意
```zyl```要开演唱会，需要从 $n$ 首歌中选出 $m$ 首。每首歌的欢乐度是所有学生从这首歌获得的快乐值之和。```zyl```会先选出欢乐度最高的 $m$ 首歌，但有一个特殊规则：如果她最喜欢的歌（她获得快乐值最高的歌）不在歌单中，就要把歌单最后一首删掉，把她最喜欢的歌加到最后。

### 解法
先算出每首歌的总欢乐度，然后排序选出最高的 $m$ 首。找到她最喜欢的歌，检查在不在歌单里。如果在就提到最前面，如果不在就删掉最后一首，把最喜欢的加到最后。
```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

struct Node {
    int id;
    long long sum;
};

bool cmp(Node x, Node y) {
    return x.sum > y.sum;
}

int main() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    
    long long h[MAXN] = {0};      // 每首歌的总欢乐度
    int her[MAXN] = {0};          // 她对每首歌的快乐值
    
    // 读入所有学生的快乐值
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            h[j] += x;           // 累加欢乐度
            if (i == b) {
                her[j] = x;      // 记录她的快乐值
            }
        }
    }
    
    Node s[MAXN];                // 歌曲列表
    for (int i = 1; i <= n; i++) {
        s[i] = {i, h[i]};
    }
    
    // 按欢乐度从高到低排序
    sort(s + 1, s + n + 1, cmp);
    
    int list[MAXN];              // 初始歌单
    for (int i = 1; i <= m; i++) {
        list[i] = s[i].id;
    }
    
    // 找她最喜欢的歌
    int fav = 1;
    int max_val = her[1];
    for (int i = 2; i <= n; i++) {
        if (her[i] > max_val) {
            max_val = her[i];
            fav = i;
        }
    }
    
    // 检查最喜欢的歌在不在歌单里
    bool found = false;
    int pos = 0;
    for (int i = 1; i <= m; i++) {
        if (list[i] == fav) {
            found = true;
            pos = i;
            break;
        }
    }
    
    if (found) {
        // 提到最前面
        for (int i = pos; i > 1; i--) {
            list[i] = list[i - 1];
        }
        list[1] = fav;
    } else {
        // 删最后一首，加最喜欢的
        list[m] = fav;
    }
    
    // 输出歌单
    for (int i = 1; i <= m; i++) {
        cout << list[i] << " ";
    }
    
    return 0;
}
```
## P12269 [蓝桥杯 2024 国 Python B] 切木棒
### 题意
有 $n$ 根木棒，可以切 $m$ 次。每次切一根木棒都会把它分成两段整数长度的木棒。问切完 $m$ 次后，最长的木棒最短能是多少。
### 解法
用二分答案的方法。猜一个最大长度 $x$ ，然后计算要把所有木棒都切成不超过 $x$ 长度需要切多少次。如果需要的次数小于等于 $m$ ，说明 $x$ 可能偏大；如果需要的次数大于 $m$ ，说明 $x$ 偏小。
```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 300005;

long long n, m;
long long a[N];

long long chk(long long x) {
    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > x) {
            long long p = (a[i] + x - 1) / x;
            cnt += p - 1;
        }
    }
    return cnt;
}

int main() {
    cin >> n >> m;
    long long mx = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > mx) mx = a[i];
    }
    
    long long l = 1, r = mx, ans = mx;
    while (l <= r) {
        long long mid = (l + r) / 2;
        long long c = chk(mid);
        if (c <= m) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    cout << ans;
    return 0;
}
```
拜！

正在渲染内容...