国产探花免费观看_亚洲丰满少妇自慰呻吟_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;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 光山县| 奉新县| 金寨县| 通城县| 巴塘县| 儋州市| 西藏| 雅江县| 安顺市| 景东| 苏尼特右旗| 响水县| 桦甸市| 蕉岭县| 华容县| 东辽县| 鹤庆县| 莱阳市| 瑞丽市| 邯郸市| 宁蒗| 涞水县| 高碑店市| 西华县| 绩溪县| 福贡县| 延安市| 恭城| 湘西| 卢龙县| 三原县| 双桥区| 汕尾市| 芮城县| 运城市| 蓝田县| 淮南市| 沂南县| 视频| 任丘市| 肃北|