大家好，歡迎閱讀周末演算法題專題。

今天選擇的演算法題是來自contest 1407比賽的C題，這題全場通過6700餘人。通過的人數雖然多，但是這題真的不簡單，想出演算法來不太容易。拋開難度不提，這道題非常非常有意思，老實說這種形式的題目我也是第一次見。

題目鏈接：//codeforces.com/contest/1407/problem/C

廢話不多說，我們來看題目。

題意

這題是一道非典型的演算法題，與其說是一道演算法題不如說更像是一個遊戲。遊戲的目的是猜一個1至n這n個數構成的排列，我們需要通過輸入和輸出和系統進行交互，從系統處獲取更多的資訊，最終給出猜測的結果。

首先系統會給定一個整數n，表示這個排列由n個數字構成，這n個數字由前n個正整數構成，也就是1到n這n個數字。之後我們可以通過輸出一個命令的形式向系統進行提問，提問的方式是? x y。系統會計算排列當中第x個數對第y個數取模的結果進行返回（排列的下標從1開始），也就是返回的值。

系統最多接受2n次詢問，當我們已經猜出整個排列之後，輸出這個排列。其中。

樣例

這個樣例要倒過來看，第一個輸入的3表示n。接著就先看輸出再看輸入。這個樣例要猜的結果是[1, 3, 2]，首先詢問了num[1]對num[2]取余的結果，系統返回是1。接著詢問num[3]對num[2]取余的結果，答案是2。接著詢問num[1]%num[3]和num[2]%num[1]，得到的結果分別是1和0。最終我們根據這些資訊猜測出了這個排列是[1, 3, 2]，通過! 1 3 2的形式進行返回。

思路

那道題之後我們首先可以發現，n確定了之後這n個數也就確定了。因為n最大，其他數對n取模都是它本身。所以我們需要先找到n的位置。

但是n的位置並不好找，想來想去只有一種辦法，就是當出現兩個數的餘數是n-1的時候，就可以確定這兩個數一個是n-1另外一個是n。但是很明顯，這樣做我們無法在規定步數內解出來。因為n個數兩兩組合一共有接近種，但是題目限定我們最多只能詢問2n次。

很顯然，先找到n再尋找其他值是不行的。

既然這個想法不行，我又開始找起了其他方法。我們求了x % y的結果之後，究竟有什麼用呢？這個結果到底有沒有其他資訊呢？

我們來簡單分析一下，我們假設x % y = 1，那麼這能說明什麼嗎？很明顯，不能說明什麼，因為可能性太多了。1對其他數取模都等於1，x % (x-1)也等於1。但假如x % y > (n/2) 呢？其實就能說明問題了。因為x和y的範圍是[1, n]，現在兩個數取模之後的結果大於n的一半，很明顯說明x就是這個結果，y是比x更大的數。還有一種情況是x % y = 0，這種情況我們雖然無法確定x和y的值，但是可以知道x一定是y的倍數且x > y。

雖然知道這些，但還是不夠解開問題，仍然需要碰運氣，因為我們並不能保證在查詢次數內剛好就可以找到所有比二分之n大的數。但是這一段分析並不是無用的，我們可以在此基礎上更進一步。我們求了x和y的餘數之後可以再求一下y和x的餘數，假設x % y = a, y % x = b，通過分析a和b我們能夠得到什麼結果呢？

首先我們可以肯定a和b不會相等，原因也很簡單，因為x和y一定不等（排列中的數各不相同）。我們不妨假設x > y，那麼y % x =b = y，x % y = a < y。如果a和b相等的話，那麼就有 y < y，這顯然是不成立的。所以可以肯定a和b一定不等。其次從上面的證明我們也看得出來，在x > y時，那麼一定可以得到a < b。因為a = x % y < y，b = y % x = y。也就是說我們可以通過a和b的關係判斷x和y的關係，不僅如此，還可以確定y的值。

到這裡距離解出這道題已經非常接近了，只差臨門一腳，但是這裡我還是走了彎路。我當時的想法是把這些數兩兩配對，這樣就可以確定出其中的一半。之後我們再把解不出來的數再進行配對，直到最後只剩下一個數為止。後來發現也有反例，比如[1, 3, 2, 4, 5]，在這個例子當中1和3配對，2和4配對，5落單。我們還是沒辦法解出來。

我在這裡苦思冥想了很久，後來才發現答案遠在天邊近在眼前，解法其實非常簡單。我們只需要從前往後遍歷維護一個最大值即可。我們假設最大值是id，凡是遇到小於id的數，都可以通過它和id取模的結果求出來。如果遇到了比id更大的數，同樣可以通過取模的結果求出id。所以到最後的時候，我們可以求出除了最大值其他的所有數，這個剩下的數就是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)]

# 一開始將最大值的下標設為1
idx = 1
for i in range(2, n+1):
    x = guess(idx, i)
    y = guess(i, idx)
    # 說明遇到了更大的數，那麼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]))))

今天的問題到這裡就結束了，衷心祝願大家每天都有所收穫。如果還喜歡今天的內容的話，請來一個三連支援吧~（點贊、關注、轉發）

原文鏈接，求個關注

本文使用 mdnice 排版

– END –