CodeForces 902A Visiting a Friend（思维、坑）

题目链接：CodeForces 902A Visiting a Friend

第一遍想的，只要 0~m 都访问了就可以，第二组样例都没过，WA

第二遍想的，只要 0~m 都访问了并且每个区间的左端点都在上一个区间之间就可以，wrong answer on test 3

网上找的题解都没看懂QAQ

把所有情况都列了一遍
CodeForces 902A Visiting a Friend（思维、坑）

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

struct point
{
    int st;		//左端点 
    int en;		//右端点 
}p[110];

int main()
{
    int n,m;
	scanf("%d%d",&n,&m);
	
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].st,&p[i].en);
    
    if(p[1].st!=0)	//第一个如果不从0开始，直接No
    {
    	printf("No\n");
    	return 0;
	}
	else
	{
		if(p[1].en>=m)	//第一个从0开始并且大于等于m，直接Yes
		{
			printf("Yes\n");
			return 0;
		}
	}
	
	bool flag=false;

    for(int i=2;i<=n;i++)
    {
    	if(p[i].st>p[i-1].en)	//如果出现上图序号5、7的情况，不能直接判断是否正确，退出循环交给flag判断
            break;
    	
		if(p[i].en<p[i-1].en)	//如果出现上图序号1的情况，更新右端点；2、3、4的情况不用更新
            p[i].en = p[i-1].en;
        
        if(p[i].en>=m)
        {
            flag = true;
            break;
        }
    }
    
    if(flag)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

理解上面思路后，再看题解：用x初始化为0，代表最远能传送的距离，然后x如果>=上一次传送点的距离，就代表猪能够连续使用传送，更新x的最大传送距离。如果x最后>=m就能拜访成功。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a,b,x;
    while(cin>>n>>m)
    {
        x=0;
        for(int i=0; i<n; i++)
        {
            cin>>a>>b;
            if(x>=a)   ///每次传送的极限应该>=上一次的传送地点
                x=max(x,b);///更新最远传送距离
        }
        printf("%s\n",x>=m?"YES":"NO"); ///如果最后的传送距离>=m就可以
    }
    return 0;
}

CodeForces 902A Visiting a Friend（思维、坑）

相关推荐