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

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

1054. The Dominant Color (20)

2019-11-11 02:27:03
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

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

2. 思路:

題意:在M*N個(gè)數(shù)中,找出占比超過(guò)一半的數(shù)字。思路:有多種方法,最普通的是用數(shù)組下標(biāo)映射數(shù)字,記錄最大值輸出。還有一種巧妙的方法,即在線處理法。題目說(shuō)存在一個(gè)主元素,即一個(gè)數(shù)超過(guò)一半。相當(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ā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 久治县| 田东县| 二连浩特市| 康平县| 长葛市| 汉源县| 罗平县| 绵阳市| 雅江县| 绥江县| 小金县| 泗洪县| 体育| 凤山县| 东港市| 绥中县| 马尔康县| 蕉岭县| 逊克县| 织金县| 通河县| 高台县| 台安县| 泰州市| 息烽县| 澎湖县| 永定县| 翁源县| 当雄县| 重庆市| 南京市| 西吉县| 交口县| 土默特左旗| 饶河县| 平遥县| 岗巴县| 铁岭市| 新泰市| 乡城县| 大宁县|