题解：CF2210B Simply Sitting on Chairs

shoe · 2026-04-24 13:03:26 · 题解

题目大意

有 n 把椅子排成一行，初始都没被标记。给你一个排列 p（长度为 n）。

你从第 1 把椅子开始，按顺序考虑每把椅子 i：

• 如果第 i 把椅子已经被标记，游戏立即结束。

• 如果第 i 把椅子没被标记，你有两个选择：

  1. 不坐，继续看下一把。

  2. 标记第 p_i 把椅子，然后继续看下一把。

当所有椅子都考虑完，或者遇到被标记的椅子时，游戏结束。需要最大化你坐下的椅子数量。

思路解析

既然安全坐下不会产生负面后果，而跳过安全坐下的椅子只会浪费机会，那么最优策略就为：对所有满足 p_i\le i 的椅子，全部选择坐下跳过不满足条件的椅子这样既能最大化坐下的数量，又不会提前结束游戏，所以答案即为此类 i 的个数。

直接用代码模拟就可以。

代码参考

#include<bits/stdc++.h>
using namespace std;
long long t,n,k,p[2000010];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        k=0;
        for(int i=1;i<=n;i++){
            cin>>p[i];
            if(p[i]<=i){//如果p[i]小于等于当前椅子编号
                k++;//则可以坐下，计数加1
            }
        }
        cout<<k<<endl;
    }
    return 0;
}

审核不易，求过！