当前位置：首页 > article >正文

报数游戏/补种未成活胡杨[E卷-hw_od]

article 2025/3/19 22:07:35

1.补种未成活胡杨

题目描述

近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。

一个月后，有M棵胡杨未能成活。

现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？

输入描述

N 总种植数量，1 <= N <= 100000

M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列，1 <= M <= N

K 最多可以补种的数量，0 <= K <= M

输出描述

最多的连续胡杨棵树

示例1

输入：
5
2
2 4
1
输出：
3
说明：
补种到2或4结果一样，最多的连续胡杨棵树都是3。

示例2

输入：
10
3
2 4 7
1
输出：
6
说明:
种第7棵树，最多连续胡杨树棵数位6（5，6，7，8，9，10）

#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
vector<int> deadTrees;
int solve(int N,int M,int K){
    set<int> deadTreesSet(deadTrees.begin(),deadTrees.end());
    int left=1,usedK=0; int maxLen=0;
    for(int right=1;right<=N;right++){
        if(deadTreesSet.count(right)){
            if(usedK<K) usedK++;
            else{
                while(left<=right){
                    if(deadTreesSet.count(left)){
                        left++;
                        break;
                    }
                    left++;
                }
            }
        }
        maxLen=max(maxLen,right-left+1);
    }
    return maxLen;
}
int main() {
    int N,M,K;
    cin>>N>>M;
    deadTrees.resize(M);
    for(int i=0;i<M;i++){
        cin>>deadTrees[i];
    }
    cin>>K;
    int maxContinuousTrees=0;
    maxContinuousTrees=solve(N,M,K);
    cout<<maxContinuousTrees<<endl;
    return 0;
}

//1 _ 3 _ 5
//1 _ 3 _ 5 6 _ 8 9 10

思路：滑窗, 直接看代码是可以看懂的

练习题目如下:
https://leetcode.cn/discuss/post/3578981/ti-dan-hua-dong-chuang-kou-ding-chang-bu-rzz7/

2.报数游戏

题目描述

100个人围成一圈，每个人有一个编码，编号从1开始到100。

他们从1开始依次报数，报到为M的人自动退出圈圈，然后下一个人接着从1开始报数，直到剩余的人数小于M。

请问最后剩余的人在原先的编号为多少？

输入描述

输入一个整数参数 M

输出描述

如果输入参数M小于等于1或者大于等于100，输出“ERROR!”；否则按照原先的编号从小到大的顺序，以英文逗号分割输出编号字符串

示例1

输入: 3 输出: 58,91

示例2

输入：4 输出：34,45,97

#include <bits/stdc++.h>
using namespace std;
void solve(int M) {
    if (M <= 1 || M > 100) {
        cout << "ERROR!" << endl;
        return;
    }
    vector<int> people;
    for (int i = 1; i <= 100; i++) people.push_back(i);
    int index = 0; 
    while ((int)people.size() >= M){
        index = (index + M - 1) % people.size();  
        people.erase(people.begin() + index);    
    }
    int n=people.size();
    //剩余人数小于M, 输出结果
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ",";
        cout << people[i];
    }
    cout << endl;
}

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