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

首頁 > 學院 > 開發設計 > 正文

1054. The Dominant Color (20)

2019-11-11 02:26:14
字體:
來源:轉載
供稿:網友

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

2. 思路:

題意:在M*N個數中,找出占比超過一半的數字。思路:有多種方法,最普通的是用數組下標映射數字,記錄最大值輸出。還有一種巧妙的方法,即在線處理法。題目說存在一個主元素,即一個數超過一半。相當于這個數的個數減去其他不同的個數仍然大于0.所以,我們可以設置一個變量cur,即當前的主元素,及它的個數cnt。在讀入數據的時候,如果相等,cnt++, 不等就自減。一旦cnt小于0的時候,那這個數cur肯定不是主元素,更換cur為當前統計的數。統計完直接輸出cur。不要用cin,超時。已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;//總個數	int cur, cnt = 1;//分別為當前顏色,個數	scanf("%d", &cur);//先讀入第一個,初始化。	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設為1				cnt = 1;			}		}	}	printf("%d/n", cur);	return 0;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 娱乐| 嘉峪关市| 五常市| 福贡县| 十堰市| 临泉县| 永泰县| 道孚县| 宜宾市| 灵武市| 定兴县| 页游| 凉山| 紫阳县| 平乐县| 安阳市| 福清市| 怀安县| 织金县| 弋阳县| 西安市| 平湖市| 贵定县| 鄱阳县| 靖安县| 松潘县| 灌阳县| 辉县市| 峡江县| 蓬莱市| 铁岭市| 黄大仙区| 平山县| 云安县| 宁南县| 东源县| 大同县| 乌兰浩特市| 尉氏县| 商河县| 光泽县|