LuoguP4263 [Code+#3]投票统计题解

Content

有 \(t\) 组询问，每组询问给定一个长度为 \(n\) 的数列，请将出现次数最多的数按照从小到大的顺序输出，或者这些数在数列中出现的次数都相等。

数据范围：\(t\) 未知，\(n\leqslant 10^5,a_i\leqslant 10^9\)。

Solution

算是比较小清新的排序题。

我们直接用 map 开个桶，统计每个数出现的次数，然后排序看哪些数出现的次数最多，然后将这些数再次从小到大排序后输出即可，注意特判一下所有数出现的次数都相等的情况。

Code

int t, n, cnt, a[100007];

struct node {

	int id, val;

	bool operator < (const node& s) const {return val > s.val;}

}kk[100007];

map<int, int> vis;

void cle() {

	_for(i, 1, cnt) vis[kk[i].id] = 0, kk[i].id = 0, kk[i].val = 0;

	cnt = 0;

}

int main() {

	getint(t);

	while(t--) {

		cle();

		getint(n);

		_for(i, 1, n) {

			int x;

			getint(x);

			if(!vis[x]) kk[++cnt].id = x, kk[cnt].val++, vis[x] = cnt;

			else kk[vis[x]].val++;

		}

		int flagofallsame = 1;

		_for(i, 2, cnt) if(kk[i].val != kk[i - 1].val) {flagofallsame = 0; break;}

		if(flagofallsame) {puts("-1"); continue;}

		sort(kk + 1, kk + cnt + 1);

		int ans[100007] = {0}, ansnum = 0;

		_for(i, 1, cnt) {if(kk[i].val == kk[1].val) ans[++ansnum] = kk[i].id; else break;}

		sort(ans + 1, ans + ansnum + 1);

		printf("%d\n", ansnum);

		_for(i, 1, ansnum) printf("%d ", ans[i]);

		puts("");

	}

	return 0;

}

巴特西

LuoguP4263 [Code+#3]投票统计题解

Content

Solution

Code

最新文章

热门文章

巴特西

LuoguP4263 [Code+#3]投票统计 题解

Content

Solution

Code

最新文章

热门文章

LuoguP4263 [Code+#3]投票统计题解