国产探花免费观看_亚洲丰满少妇自慰呻吟_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ā)表
主站蜘蛛池模板: 海林市| 丰宁| 宣汉县| 怀安县| 项城市| 蓬溪县| 太仆寺旗| 湘潭市| 东兰县| 禹州市| 都安| 蒙山县| 开远市| 青海省| 建湖县| 阿拉善左旗| 婺源县| 彰化市| 岳阳县| 通道| 盘锦市| 宜兰市| 滦南县| 湘潭市| 万山特区| 德格县| 淳安县| 岚皋县| 宁远县| 昌平区| 静宁县| 陇南市| 孟津县| 永康市| 乐亭县| 景东| 九江市| 剑川县| 淮南市| 宁化县| 邯郸市|