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

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

1054. The Dominant Color (20)

2019-11-11 01:54: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ā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 陇川县| 卢龙县| 玉田县| 临潭县| 德昌县| 抚顺市| 凤翔县| 铅山县| 定日县| 涞源县| 龙游县| 太和县| 江永县| 济宁市| 沅陵县| 磐石市| 锡林郭勒盟| 新安县| 科技| 定日县| 平谷区| 宁化县| 景东| 漳平市| 封开县| 武川县| 泰安市| 阳西县| 高要市| 黎川县| 保靖县| 得荣县| 弥渡县| 武定县| 西充县| 金门县| 铅山县| 宿松县| 新余市| 浙江省| 北宁市|