[COCI2017-2018#5] Karte，簡短的代碼想到了就AC

這道題是SPJ放心搞
但是我的腦子里面的東西，不用我多說，你們就知道是水和面粉和成的
看招 題

【題目描述】
你有一副共有N張牌的牌，在第i張牌上會有一個數字ai表示在這張牌下面至少一共有ai張牌上的信息是假的。接下來你需要對這副牌進行洗牌，使得這副牌當中，恰好有K張牌的信息是錯誤的。

【輸入輸出格式】
第一行輸入兩個數字N、K（1≤N≤5105，0≤K≤N）。
接下來N行，每行輸入一個數字，表示第i張牌上的數字ai（0≤ai≤5105）

如果不存在恰好K張牌上的信息是錯誤的情況，則輸出-1，否則，將這副牌從上往下輸出這N張牌上的所對應的ai。如果有多種答案，輸出任意一種。

【樣例】
樣例輸入1
4 2
1
2
2
3
樣例輸出1
2 3 1 2
樣例輸入2
5 3
2
1
3
0
3
樣例輸出2
3 3 0 1 2
樣例輸入3
6 4
0
2
5
2
0
1
樣例輸出3
-1

【樣例分析】
對于樣例2：第5張牌后沒有牌，所以他后面是錯誤的牌的數量應該是0，但他是2，所以這張牌是錯誤的。第4牌后面有1張牌是錯誤的(第5張)，它上面寫的是1，所以是正確的。第3張牌上寫的是0，它后面有1張牌是錯誤的（第5張），所以它是正確的（題目說的是至少有，不是確定有）。第2張牌上面寫的是3，但它后面只有一張是錯誤的（第5張）所以是錯誤的。第1張牌上寫的是3，但它后面只有2張是錯誤的（第2張和第5張），所以是錯誤的。即一共有3張是錯誤的。

【正解】
把a數組進行從小到大sort然后把n-k+1到n的值逆序倒過來存儲
再用一個for循環從后往前判斷錯誤信息個數最后按照題意輸出就行了
完啦！這道題就可以AC了
但是作為一個有良心的大大！
我必須證明威懾么！！
1）如果錯誤信息個數<k，因為只有在ai越大而i又越靠前的時候ai才更大幾率的錯，我們按照最大幾率去排序，個數都不夠，那么其他方案一樣也不夠
2）如果錯誤信息個數>k，就意味著n-k+1到n之間一定所有都是錯誤的信息，假設在n-k+1到n之間有一個i的信息是正確的，而1到n-k中每一個aj值都小于ai，那么它們的信息也一定是正確的，個數就不可能大于k，故假設不成立。那么如果我們交換i，j是否會減少k呢？過來人告訴不會，k只可能不變或者+1.因為如果我們換了i，j，j本身就是正確的，換過來了有可能也是正確，甚至是錯誤的導致k+1，而i換過去了前面錯誤的個數也不會變，就算j導致k+1使得i正確的話，k再-1也是不變，所以不管怎樣都不會使得k最少

好了，話不多說，屁不多放，上馬
【代碼實現】

#include <cstdio> #include <algorithm> using namespace std; #define MAXN 500005 int n, k; int a[MAXN], b[MAXN]; int main() {scanf ( "%d %d", &n, &k );for ( int i = 1;i <= n;i ++ )scanf ( "%d", &a[i] );sort ( a + 1, a + n + 1 );int cnt = 0;for ( int i = 1;i <= n - k;i ++ )b[++ cnt] = a[i];for ( int i = n;i >= n - k + 1;i -- )b[++ cnt] = a[i];cnt = 0;for ( int i = n;i >= 1;i -- )if ( b[i] > cnt ) cnt ++;if ( cnt == k )for ( int i = 1;i <= n;i ++ )printf ( "%d\n", b[i] );else printf ( "-1" );return 0; }

平A小王子，AWM一槍爆掉你的三級頭

不懂的地方，歡迎各位xjj，xgg留言，bye~~

總結

以上是生活随笔為你收集整理的[COCI2017-2018#5] Karte的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。