西安网站建设流程,商丘网络推广公司,如何做外链,郑州做网站建设公司第一题#xff1a;MAJORITY OPINION
标签#xff1a;思维、模拟
题意#xff1a;给定一个长度为 n n n的序列 a a a#xff0c;操作#xff1a;若区间 [ i , j ] [i,j] [i,j]内某个数字 k k k出现的次数 大于区间长度的一半#xff0c;可以将区间内的所有数都换成这个数…第一题MAJORITY OPINION
标签思维、模拟
题意给定一个长度为 n n n的序列 a a a操作若区间 [ i , j ] [i,j] [i,j]内某个数字 k k k出现的次数 大于区间长度的一半可以将区间内的所有数都换成这个数 k k k。经过多次操作之后让区间 [ 1 , n ] [1,n] [1,n]内都为同一个数输出所有可能的数按照数字递增的顺序若没有输出 − 1 -1 −1。 1 n 1 0 5 , 1 a i n 1n10^5,1a_in 1n105,1ain
题解连续两个相同的数不管是往前还是往后一个都可以把加进来的数变成区间内的这个数。比如 x y y z x\ y \ y \ z x y y z可以往前把 x x x变成 y y y往后把 z z z变成 y y y那其实再往前或者再往后 可以把所有数都变成 y y y。除此之外还有 y x y y \ x\ y y x y的情况也是满足条件的先把中间的这个 x x x变成 y y y然后也可以把所有数都变成 y y y。最终就变成了求第 i i i数和 第 i − 1 i-1 i−1个数或者第 i − 2 i-2 i−2个数 是否相同相同的话就可以去作为我们的答案当然可能有重复的情况所以要去重输出。代码
#include bits/stdc.h
using namespace std;const int N 1e5 10;
int t, n, a[N], res[N];int main() {cin t;while (t--) {cin n;int c 0;for (int i 1; i n; i) {cin a[i];if (i 2 a[i] a[i - 1]) res[c] a[i];else if (i 3 a[i] a[i - 2]) res[c] a[i];}sort(res 1, res 1 c);c unique(res 1, res 1 c) - res - 1;if (c 0) cout -1 endl;else {for (int i 1; i c; i) {cout res[i] ;}cout res[c] endl;}}return 0;
}
