牛客NOIP暑期七天营-普及组3-C区间中最多的数
区间中最多的数
https://ac.nowcoder.com/acm/contest/927/C
题目大意:给定n个数,q次询问,每次问区间[l, r]直接出现最多的数字是什么?并列的话输出较大数。
从数据范围看,O(qn)超时,O(qa)不超时。
空间限制128M,开一个100*200000的数组刚好不超时。
预处理每种数字出现的前缀和,对于每个循环,分别O(1)求出每种数字的数量,记录最优值即可。
(c[i][j]表示数字i在[1, j]出现的次数。)
#include <stdio.h> int n, m, i, j, k, x, y; int c[105][200005], d[105]; int main(){ scanf("%d%d", &n, &m); for(i=1; i<=n; i++){ scanf("%d", &k); c[k][i] = 1; } for(i=1; i<=100; i++){ for(j=1; j<=n; j++){ c[i][j] += c[i][j-1]; } } while(m--){ scanf("%d%d", &x, &y); for(i=k=1; i<=100; i++){ d[i] = c[i][y] - c[i][x-1]; if(d[i] >= d[k]) k = i; } printf("%d\n", k); } return 0; }