国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

1054. The Dominant Color (20)

2019-11-11 03:47:00
字體:
供稿:網(wǎng)友

1. 原題: https://www.patest.cn/contests/pat-a-PRactise/1054

2. 思路:

題意:在M*N個(gè)數(shù)中,找出占比超過一半的數(shù)字。思路:有多種方法,最普通的是用數(shù)組下標(biāo)映射數(shù)字,記錄最大值輸出。還有一種巧妙的方法,即在線處理法。題目說存在一個(gè)主元素,即一個(gè)數(shù)超過一半。相當(dāng)于這個(gè)數(shù)的個(gè)數(shù)減去其他不同的個(gè)數(shù)仍然大于0.所以,我們可以設(shè)置一個(gè)變量cur,即當(dāng)前的主元素,及它的個(gè)數(shù)cnt。在讀入數(shù)據(jù)的時(shí)候,如果相等,cnt++, 不等就自減。一旦cnt小于0的時(shí)候,那這個(gè)數(shù)cur肯定不是主元素,更換cur為當(dāng)前統(tǒng)計(jì)的數(shù)。統(tǒng)計(jì)完直接輸出cur。不要用cin,超時(shí)。已AC。

3. 源碼(已AC):

#include<iostream>using namespace std;int main(void){	//freopen("in.txt", "r", stdin);	int M, N;	scanf("%d %d", &M, &N);	int num = M*N;//總個(gè)數(shù)	int cur, cnt = 1;//分別為當(dāng)前顏色,個(gè)數(shù)	scanf("%d", &cur);//先讀入第一個(gè),初始化。	for (int i = 1; i < num; i++)	{		int tem;		scanf("%d", &tem);		if (cur == tem)//相等,自增			cnt++;		else		{			cnt--;			if (cnt < 0)			{				cur = tem;//小于0,更換主元素,cnt設(shè)為1				cnt = 1;			}		}	}	printf("%d/n", cur);	return 0;}
發(fā)表評論 共有條評論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 离岛区| 乐亭县| 河北省| 寻乌县| 古交市| 新蔡县| 崇明县| 凤山县| 杭锦旗| 大安市| 若尔盖县| 英山县| 和政县| 革吉县| 辛集市| 望城县| 嵊泗县| 文山县| 泰安市| 大余县| 阿坝县| 青岛市| 鲁甸县| 高淳县| 陈巴尔虎旗| 阿克陶县| 白城市| 白山市| 上饶县| 文昌市| 德安县| 张家港市| 绥芬河市| 莱州市| 临汾市| 新源县| 灌云县| 栖霞市| 桦川县| 铜山县| 深水埗区|