Educational Codeforces Round 55 (Rated for Div. 2) A - Vasya and Book

时间:2023-03-09 13:31:40
Educational Codeforces Round 55 (Rated for Div. 2) A - Vasya and Book

传送门

https://www.cnblogs.com/violet-acmer/p/10035971.html

题意:

  一本书有n页,每次只能翻 d 页,问从x页到y页需要翻动几次?

  注意:往前翻最少翻到第1页,往后翻最多翻到n页。

题解:

  一开始想找规律来着,emmmm,直接用广搜,当时竟然过了,第二天,加数据了,直接就TLE了。

  然后,今天下午,mxl给我和lk讲了一下ta的做法,找的规律,啊啊啊,我竟然没想到。

  规律:

  (1):如果abs(x-y)%d == 0,那么,那么直接输出abs(x-y)/d;

  (2):如果abs(x-y)%d != 0,并且(y-1)%d != 0 && (n-y)%d != 0,输出-1。

      对(2)的理解:如果abs(x-y)%d != 0,说明不可能从x直接翻到y,那么,只能通过从 x ->1 -> y 或 x -> n -> y了,但如果1不能翻到y并且n也不能翻到y,那肯定

    就不会从x翻到y了,所以输出-1。

  (3):如果前两种情况都不满足,说明 x 可以通过 (x ->1 -> y) 或 (x -> n -> y) 翻到y,然后,只需输出两中方式的最少翻动的次数即可。

AC代码:

 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f int n,x,y,d; int Solve()
{
int sub=abs(x-y);//规律(1)
if(sub%d == )
return sub/d;
if((y-)%d != && (n-y)%d != )//规律(2)
return -; int xToOne=(x-)/d+((x-)%d == ? :);
int oneToY=((y-)%d == ? (y-)/d:INF);//注意:此处是判断能否有1到y,如果不能,赋值为INF int xToN=(n-x)/d+((n-x)%d == ? :);
int nToY=((n-y)%d == ? (n-y)/d:INF);//同上 return min(xToOne+oneToY,xToN+nToY);//规律(3)
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&x,&y,&d);
printf("%d\n",Solve());
}
return ;
}