Google Code Jam 2011 Qualification Round D. GoroSort

GCJ

GoroSort

揃っている数字を押さえて机を叩くという戦略を考えると、n個の間違いがあった時、期待値はn回。サンプル最後のような叩き方もできるけど、揃っていない数字をどのように分けても合計はn回になるはず。

for t in range(input()):
    input()
    C = map(int,raw_input().split())
    n = 0
    for i in range(len(C)):
        if C[i]!=i+1:
            n += 1
    print "Case #%s: %s" % (t+1,n)