今天選擇的算法題是來自contest 1407比賽的C題，這題全場(chǎng)通過6700余人。通過的人數(shù)雖然多，但是這題真的不簡(jiǎn)單，想出算法來不太容易。拋開難度不提，這道題非常非常有意思，老實(shí)說這種形式的題目我也是第一次見。
題目鏈接：https://codeforces.com/contest/1407/problem/C
廢話不多說，我們來看題目。
題意
這題是一道非典型的算法題，與其說是一道算法題不如說更像是一個(gè)游戲。游戲的目的是猜一個(gè)1至n這n個(gè)數(shù)構(gòu)成的排列，我們需要通過輸入和輸出和系統(tǒng)進(jìn)行交互，從系統(tǒng)處獲取更多的信息，最終給出猜測(cè)的結(jié)果。
首先系統(tǒng)會(huì)給定一個(gè)整數(shù)n，表示這個(gè)排列由n個(gè)數(shù)字構(gòu)成，這n個(gè)數(shù)字由前n個(gè)正整數(shù)構(gòu)成，也就是1到n這n個(gè)數(shù)字。之后我們可以通過輸出一個(gè)命令的形式向系統(tǒng)進(jìn)行提問，提問的方式是? x y。系統(tǒng)會(huì)計(jì)算排列當(dāng)中第x個(gè)數(shù)對(duì)第y個(gè)數(shù)取模的結(jié)果進(jìn)行返回（排列的下標(biāo)從1開始），也就是返回
num[x] % num[y] 的值。
系統(tǒng)最多接受2n次詢問，當(dāng)我們已經(jīng)猜出整個(gè)排列之后，輸出這個(gè)排列。其中n <= 1e4。
樣例
這個(gè)樣例要倒過來看，第一個(gè)輸入的3表示n。接著就先看輸出再看輸入。這個(gè)樣例要猜的結(jié)果是[1, 3, 2]，首先詢問了num[1]對(duì)num[2]取余的結(jié)果，系統(tǒng)返回是1。接著詢問num[3]對(duì)num[2]取余的結(jié)果，答案是2。接著詢問num[1]%num[3]和num[2]%num[1]，得到的結(jié)果分別是1和0。最終我們根據(jù)這些信息猜測(cè)出了這個(gè)排列是[1, 3, 2]，通過! 1 3 2的形式進(jìn)行返回。
思路
那道題之后我們首先可以發(fā)現(xiàn)，n確定了之后這n個(gè)數(shù)也就確定了。因?yàn)閚最大，其他數(shù)對(duì)n取模都是它本身。所以我們需要先找到n的位置。
但是n的位置并不好找，想來想去只有一種辦法，就是當(dāng)出現(xiàn)兩個(gè)數(shù)的余數(shù)是n-1的時(shí)候，就可以確定這兩個(gè)數(shù)一個(gè)是n-1另外一個(gè)是n。但是很明顯，這樣做我們無法在規(guī)定步數(shù)內(nèi)解出來。因?yàn)閚個(gè)數(shù)兩兩組合一共有接近n^2種，但是題目限定我們最多只能詢問2n次。
很顯然，先找到n再尋找其他值是不行的。
既然這個(gè)想法不行，我又開始找起了其他方法。我們求了x % y的結(jié)果之后，究竟有什么用呢？這個(gè)結(jié)果到底有沒有其他信息呢？
我們來簡(jiǎn)單分析一下，我們假設(shè)x % y = 1，那么這能說明什么嗎？很明顯，不能說明什么，因?yàn)榭赡苄蕴嗔恕?對(duì)其他數(shù)取模都等于1，x % (x-1)也等于1。但假如x % y > (n/2) 呢？其實(shí)就能說明問題了。因?yàn)閤和y的范圍是[1, n]，現(xiàn)在兩個(gè)數(shù)取模之后的結(jié)果大于n的一半，很明顯說明x就是這個(gè)結(jié)果，y是比x更大的數(shù)。還有一種情況是x % y = 0，這種情況我們雖然無法確定x和y的值，但是可以知道x一定是y的倍數(shù)且x > y。
雖然知道這些，但還是不夠解開問題，仍然需要碰運(yùn)氣，因?yàn)槲覀儾⒉荒鼙ＷC在查詢次數(shù)內(nèi)剛好就可以找到所有比二分之n大的數(shù)。但是這一段分析并不是無用的，我們可以在此基礎(chǔ)上更進(jìn)一步。我們求了x和y的余數(shù)之后可以再求一下y和x的余數(shù)，假設(shè)x % y = a, y % x = b，通過分析a和b我們能夠得到什么結(jié)果呢？
首先我們可以肯定a和b不會(huì)相等，原因也很簡(jiǎn)單，因?yàn)閤和y一定不等（排列中的數(shù)各不相同）。我們不妨假設(shè)x > y，那么y % x =b = y，x % y = a < y。如果a和b相等的話，那么就有 y < y，這顯然是不成立的。所以可以肯定a和b一定不等。其次從上面的證明我們也看得出來，在x > y時(shí)，那么一定可以得到a < b。因?yàn)閍 = x % y < y，b = y % x = y。也就是說我們可以通過a和b的關(guān)系判斷x和y的關(guān)系，不僅如此，還可以確定y的值。
到這里距離解出這道題已經(jīng)非常接近了，只差臨門一腳，但是這里我還是走了彎路。我當(dāng)時(shí)的想法是把這些數(shù)兩兩配對(duì)，這樣就可以確定出其中的一半。之后我們?cè)侔呀獠怀鰜淼臄?shù)再進(jìn)行配對(duì)，直到最后只剩下一個(gè)數(shù)為止。后來發(fā)現(xiàn)也有反例，比如[1, 3, 2, 4, 5]，在這個(gè)例子當(dāng)中1和3配對(duì)，2和4配對(duì)，5落單。我們還是沒辦法解出來。
我在這里苦思冥想了很久，后來才發(fā)現(xiàn)答案遠(yuǎn)在天邊近在眼前，解法其實(shí)非常簡(jiǎn)單。我們只需要從前往后遍歷維護(hù)一個(gè)最大值即可。我們假設(shè)最大值是id，凡是遇到小于id的數(shù)，都可以通過它和id取模的結(jié)果求出來。如果遇到了比id更大的數(shù)，同樣可以通過取模的結(jié)果求出id。所以到最后的時(shí)候，我們可以求出除了最大值其他的所有數(shù)，這個(gè)剩下的數(shù)就是n。
想通了真的非常非常簡(jiǎn)單，說穿了一錢不值，但是要靠自己想明白還是不太容易的。并且這道題的題目形式也很新穎，非常非常有趣，適合在周末一玩。
最后，我們來看代碼：
import sys
def guess(x, y):
print('? {} {}'.format(x, y))
# 輸出之后需要flush一下，防止影響輸入
sys.stdout.flush()
st = input()
return int(st)
st = input()
n = int(st)
num = [-1 for _ in range(n+2)]
# 一開始將最大值的下標(biāo)設(shè)為1
idx = 1
for i in range(2, n+1):
x = guess(idx, i)
y = guess(i, idx)
# 說明遇到了更大的數(shù)，那么x就是之前的最大值
if x > y:
num[idx] = x
idx = i
# 否則求出來的就是i
else:
num[i] = y
num[idx] = n
print('! {}'.format(' '.join(map(str, num[1:n+1]))))
今天的問題到這里就結(jié)束了，衷心祝愿大家每天都有所收獲。如果還喜歡今天的內(nèi)容的話，請(qǐng)來一個(gè)三連支持吧~（點(diǎn)贊、關(guān)注、轉(zhuǎn)發(fā)）
- END -
本文始發(fā)于公眾號(hào)：TechFlow，求個(gè)關(guān)注
