• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

题解 CF1082A 【Vasya and Book】

开发技术 开发技术 2周前 (04-08) 7次浏览

Content

给定 (T) 组数据,每组数据给出四个整数 (n,x,y,d)。小 V 有一本 (n) 页的书,每次可以恰好翻 (d) 页,求从第 (x) 页恰好翻到第 (y) 页的最少次数,或者报告不存在这样的方案。

数据范围:(1leqslant n,dleqslant 10^9)(1leqslant x,yleqslant n)(1leqslant tleqslant 10^3)

Solution

分类讨论题。

  • 如果 (|x-y|bmod d=0),那么从第 (x) 页直接可以翻到第 (y) 页,那么 (dfrac{|y-x|}{d}) 可作为一个答案。
  • 如果 ((y-1)bmod d=0),那么可以从第 (x) 页先翻到第 (1) 页,再翻到第 (y) 页,那么 (dfrac{x-1}{d}+dfrac{y-1}{d}+[(x-1)bmod dneq 0]) 可作为一个答案。
  • 如果 ((n-y)bmod d=0),那么可以从第 (x) 页先翻到第 (n) 页,再翻到第 (y) 页,那么 (dfrac{n-x}{d}+dfrac{n-y}{d}+[(n-y)bmod dneq 0]) 可作为一个答案。

如果三种情况都不符合就输出 -1,否则输出满足情况的答案中的较小值。

Code

int main() {
	MT {
		int n = Rint, x = Rint, y = Rint, d = Rint, ans = 0x3f3f3f3f;
		if(!(abs(y - x) % d)) ans = min(ans, abs(y - x) / d);
		if(!((y - 1) % d)) ans = min(ans, (x - 1) / d + (y - 1) / d + (bool)((x - 1) % d));
		if(!((n - y) % d)) ans = min(ans, (n - x) / d + (n - y) / d + (bool)((n - y) % d));
		println(ans == 0x3f3f3f3f ? -1 : ans);
	}
    return 0;
}

程序员灯塔
转载请注明原文链接:题解 CF1082A 【Vasya and Book】
喜欢 (0)