国产探花免费观看_亚洲丰满少妇自慰呻吟_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ā)表
主站蜘蛛池模板: 东山县| 汉阴县| 若羌县| 互助| 昌平区| 陇南市| 五家渠市| 囊谦县| 繁昌县| 昆明市| 九寨沟县| 沛县| 宜都市| 紫阳县| 城固县| 汉沽区| 中西区| 大英县| 桐柏县| 德安县| 酒泉市| 黎川县| 法库县| 华宁县| 新安县| 尚志市| 万全县| 利川市| 革吉县| 行唐县| 五家渠市| 巴彦淖尔市| 怀柔区| 花莲市| 常德市| 公主岭市| 日照市| 万山特区| 信丰县| 桂阳县| 东莞市|