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)存不足，以至于無法開int數(shù)組。于是只能邊讀入邊處理。

又因?yàn)樗蟮倪@個(gè)數(shù)出現(xiàn)頻率大于一半，也就是說這個(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, 無法再抵消。因此答案為4.

怎樣實(shí)現(xiàn)呢？

只需開3個(gè)變量即可。類似于一個(gè)棧。

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

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

3. 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; }

總結(jié)

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

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