【算法学习笔记】73.数学规律题 SJTU OJ 1058 小M的机器人

Description

小M有很多个机器人,他们要么一直说真话,要么一直说假话。

然后每个人都说:

(1). 不到N个人比我工作得多

(2). 至少M个人的工资比我高。

保证没有两个人的工作一样重,也没有两个人的工资一样高,问至少有多少机器人?

Input Format

一行两个数整数N, M (  1N,M < 2^31)

Output Format

一个整数K表示至少有K个人

Hint

想不出来的同学... 不要想得太复杂了...

Sample Input

2 2

Sample Output

4



注意 这里的2 2 表示的是每个人的说话,不是某一个人。


线索一:不到N个人比我的工作多。
我们可以知道说真话的人数是N
证明:
可以认为排序之后前面有N个空,所以前N个人必须说的是真话,而且只有他们说真话。(反证法,如果排在前N个人里的某一个说了假话,表示在他前面的人有大于等于N个,与条件不符)
如果总人数小于N:
  假设有x个 x<N,则x个人说的都是真话,那么在工资列表里因为都是真话所以第一个人前面还至少有M个人,与总人数是x以矛盾。
所以总人数至少为N:
线索二和线索一类似
所以M+N即可
数学规律题。。
  
  


原文地址:https://www.cnblogs.com/yuchenlin/p/sjtu_oj_1058.html