BZOJ 2456 mode

手動(dòng)博客搬家: 本文發(fā)表于20170807 22:39:29, 原地址https://blog.csdn.net/suncongbo/article/details/76862425

URL: http://www.lydsy.com/JudgeOnline/problem.php?id=2456

題目大意：
給定一個(gè)長(zhǎng)為n (1<=n<=5e5)的數(shù)列，已知有且僅有一個(gè)數(shù)在數(shù)列中出現(xiàn)的次數(shù)>n/2, 求這個(gè)數(shù)。
注：內(nèi)存限制1MB.

思路分析：
內(nèi)存不足，以至于無(wú)法開int數(shù)組。于是只能邊讀入邊處理。
又因?yàn)樗蟮倪@個(gè)數(shù)出現(xiàn)頻率大于一半，也就是說(shuō)這個(gè)數(shù)出現(xiàn)的次數(shù)大于其他所有數(shù)出現(xiàn)的次數(shù)的總和。
因此，我們可以將不同的數(shù)“抵消”掉。
比如對(duì)于4 4 5 5 6 4 4 4 7 4 4這個(gè)長(zhǎng)度為11的序列，我們將進(jìn)行以下的抵消處理：

?(1) 4 4 5 5 6 4 4 4 7 4 4 (2) 4 5 6 4 4 4 7 4 4 //neutralize 4,5 (3) 6 4 4 4 7 4 4 //neutralize 4,5 (4) 4 4 7 4 4 //neutralize 6,4 (5) 4 4 4 //neutralize 4,7?

最后剩下的數(shù)列僅有4, 無(wú)法再抵消。因此答案為4.
只需開3個(gè)變量即可。類似于一個(gè)棧。

num存儲(chǔ)當(dāng)前棧中剩余元素的個(gè)數(shù)。

x存儲(chǔ)當(dāng)前讀入的元素。

now存儲(chǔ)讀入前的棧頂元素。
讀入后，將now與x進(jìn)行匹配，若不同則抵消。

代碼呈現(xiàn)：
(Time: 380MS; Memory: 820KB; Code: 356B)

? #include<cstdio> using namespace std;int main() {int n,now,x,num;while(scanf("%d",&n) != EOF){num = 0;for(int i=1; i<=n; i++){scanf("%d",&x);if(num == 0){num++;now = x;continue;}if(x == now) num++;else num--;}printf("%d\n",now);}return 0; } ? 發(fā)表于 2018-12-26 22:29 suncongbo 閱讀(...) 評(píng)論(...) 編輯 收藏 刷新評(píng)論刷新頁(yè)面返回頂部

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2456 mode的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。