题解：P13959 [ICPC 2023 Nanjing R] 计数器

lin_A_chu_K_fan · 2025-09-07 10:31:56 · 题解

题目传送门

题意

很直白，描述一个计数器，只有增加一和归零两种操作，给定 m 个约束条件，问能否全部满足（怎么感觉这一段好没用）

思路

首先，显而易见的，需要把输入数据按时间（题目里的 a_i）排序，然后对于每个 i 满足 1 \le i \le m，有以下两种情况：

• 若 b_i-b_{i-1}=a_i-a_{i-1}，则可以一直按加号。
• 第二种的情况条件需要注意，只要不满足前一种条件，无论如何，必须使用归零键。首先，通过求出 a_i-a_{i-1}-1 可以求出最多可以按加号的次数（减一是因为要归零），如果这个数大于等于 b_i，则可以满足条件，否则不能

通过循环统计条件可行性，在一个数据中，只要有至少一组输入不满足，则输出 No，否则输出 Yes。

代码来喽

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b;
};
node v[100005];
bool cmp(node x,node y){return x.a<y.a;}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>v[i].a>>v[i].b;
        }
        sort(v+1,v+m+1,cmp);
        bool flag=1;
        for(int i=1;i<=m;i++){
            if(v[i].a-v[i-1].a==v[i].b-v[i-1].b){flag=1;}
            else{
                if(v[i].a-v[i-1].a-1>=v[i].b)flag=1;
                else{flag=0;break；}
            }
        }
        if(flag)cout<<"Yes";
        else cout<<"No";
        cout<<endl;
    }
}

温馨提示：代码经过改动，有防抄袭措施，切勿直接复制，切勿直接复制，会编译错误！