题解：洛谷 P10131 [USACO24JAN] Majority Opinion B

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P10131 [USACO24JAN] Majority Opinion B - 洛谷【题目描述】Farmer John 有一项重要的任务——弄清楚要为他的奶牛们购买什么类型的干草。Farmer John 的N NN头奶牛2 ≤ N ≤ 10 5 2\le N\le 10^52≤N≤105编号为1 11到N NN每头奶牛喜欢恰好一种类型的干草h i h_ihi​1 ≤ h i ≤ N 1\le h_i\le N1≤hi​≤N。他希望他的所有奶牛都喜欢同一种干草。为了实现这一目标Farmer John 可以主持焦点小组访谈。一次焦点小组访谈为让编号从i ii到j jj的连续范围内的所有奶牛聚集在一起参加一次访谈。如果有一种干草是小组中超过一半的奶牛喜欢的则此次焦点小组访谈结束后所有奶牛最终都会喜欢这种干草。如果不存在这种类型的干草那么奶牛们不会改变她们喜欢的干草类型。例如在由16 1616头奶牛组成的焦点小组访谈中需要有其中9 99头或更多的奶牛具有相同的干草喜好才能使其余奶牛改变其喜好以与之一致。Farmer John 想知道哪些类型的干草有可能变为同时受到所有奶牛的喜爱。他一次只能主持一个焦点小组访谈但为了使所有奶牛都喜欢同一类型的干草他可以根据需要任意多次地主持焦点小组访谈。【输入】输入的第一行包含一个整数T TT为独立的测试用例的数量1 ≤ T ≤ 10 1\le T\le 101≤T≤10。每一个测试用例的第一行包含N NN。第二行包含N NN个整数为奶牛们喜爱的干草类型h i h_ihi​。输入保证所有测试用例的N NN之和不超过2 ⋅ 10 5 2\cdot 10^52⋅105。【输出】输出T TT行对于每个测试用例输出一行。如果可能使所有奶牛同时喜欢同一种干草则以升序输出所有可能的此类干草的类型否则输出− 1 -1−1。在同一行内输出一列整数时相邻的数用空格分隔并确保行末没有多余空格。【输入样例】5 5 1 2 2 2 3 6 1 2 3 1 2 3 6 1 1 1 2 2 2 3 3 2 3 2 2 1【输出样例】2 -1 1 2 3 -1【核心思想】问题分析给定一个长度为N NN的喜好数组h i h_ihi​值域1.. N 1..N1..N每次操作可以选择一个连续区间[ l , r ] [l, r][l,r]若区间内存在某种喜好值出现次数严格超过区间长度的一半则区间内所有奶牛都会变成该喜好值。可以反复操作任意次。问最终能否使所有奶牛喜好统一并输出所有可能统一的喜好值。关键观察由于每次操作只改变一个区间且需要严格多数那么任何能够通过一系列操作传播开的喜好值必然在原始数组中存在一个长度为 2 或 3 的“种子”——即存在相邻两个相同或间隔一个相同形如x y x。因为一个值要在一个区间内成为多数该区间内至少有两个该值相邻或间隔不超过 1 个位置否则无法形成多数。一旦这样的种子出现就可以通过反复操作将该值向两侧扩展最终覆盖整个数组。因此只需检查所有长度为 2 和 3 的子串中是否有重复元素并标记这些元素为可能答案。算法选择扫描 标记遍历数组检查所有长度为 2 的相邻对( h i , h i 1 ) (h_i, h_{i1})(hi​,hi1​)和长度为 3 的连续三元组( h i , h i 1 , h i 2 ) (h_i, h_{i1}, h_{i2})(hi​,hi1​,hi2​)。若其中存在重复元素即h i h i 1 h_i h_{i1}hi​hi1​或h i h i 2 h_i h_{i2}hi​hi2​或h i 1 h i 2 h_{i1} h_{i2}hi1​hi2​则将该重复值标记为“可行”。最后输出所有被标记的值升序若没有则输出-1。关键步骤读入数据读取T TT对每个测试用例读入N NN和数组h [ 1.. N ] h[1..N]h[1..N]。初始化标记数组用布尔数组vis[1..N]记录哪些喜好值可行。扫描对i ii从 1 到N − 2 N-2N−2若h i h i 1 h_i h_{i1}hi​hi1​标记vis[h_i] true。若h i h i 2 h_i h_{i2}hi​hi2​标记vis[h_i] true。若h i 1 h i 2 h_{i1} h_{i2}hi1​hi2​标记vis[h_{i1}] true。特判N 2 N2N2单独处理若两数相同则输出该数否则-1。输出按升序收集所有vis为真的值输出若无则输出-1。时间/空间复杂度时间复杂度O ( N ) O(N)O(N)每个测试用例线性扫描。空间复杂度O ( N ) O(N)O(N)用于标记数组和存储输入。贪心 局部传播的核心思想传播的可达性一个值x xx能够最终统一整个数组当且仅当在原始数组中存在一对相邻的x xx即x x或一个长度为 3 的x y x模式。因为若存在x x以这两个x xx为中心可以逐步向左或向右扩展区间每次扩展一个位置只要当前区间内x xx的数量超过一半最终覆盖整个数组。若存在x y x同理这两个x xx也可作为种子。反之若数组中没有任何长度为 2 或 3 的模式含有x xx则任何包含x xx的区间中x xx的数量都不可能超过一半因为x xx之间至少相隔两个其他值因此x xx无法成为多数也无法扩展。充分性一旦选定种子通过反复选择包含种子和相邻位置的区间可以逐步“感染”整个数组最终使所有值变为x xx。适用场景适用于“多数传播”模型其中某值在区间内达到严格多数即可同化整个区间。核心是识别能形成多数的最小局部模式。【算法标签】#普及- #数学【代码详解】#includebits/stdc.husingnamespacestd;intT;// 测试用例的数量intn;// 每个测试用例的数字个数inta[100005];// 存储输入的数字序列intb[100005];// 标记数组记录哪些数字满足条件intmain(){// 输入测试用例数量cinT;// 处理每个测试用例for(intt1;tT;t){// 清空数组重置为0memset(a,0,sizeof(a));memset(b,0,sizeof(b));// 输入数字个数cinn;// 输入数字序列for(inti1;in;i){cina[i];}// 特殊情况处理当n2时if(n2a[1]!a[2]){// 只有两个数字且不相等无解cout-1endl;continue;// 跳过后续处理}elseif(n2a[1]a[2]){// 只有两个数字且相等直接输出该数字couta[1]endl;continue;// 跳过后续处理}// 遍历序列检查满足条件的数字for(inti1;in-1;i){// 检查连续三个数字的相等关系// 情况1相邻两个数字相等if(a[i]a[i1]){b[a[i]]1;// 标记该数字满足条件}// 情况2间隔一个数字相等i和i2if(a[i]a[i2]){b[a[i]]1;// 标记该数字满足条件}// 情况3后两个数字相等i1和i2if(a[i1]a[i2]){b[a[i1]]1;// 标记该数字满足条件}}intflag0;// 标记是否找到满足条件的数字string s;// 用于构建输出字符串// 遍历所有可能的数字1到100000for(inti1;i100000;i){// 如果当前数字被标记为满足条件if(b[i]!0){// 将数字添加到输出字符串sto_string(i);s ;flag1;// 设置找到标志}}// 移除最后一个空格ss.substr(0,s.length()-1);// 根据是否找到结果输出if(flag){coutsendl;// 输出所有满足条件的数字}else{cout-1endl;// 无解情况}}return0;}【运行结果】5 5 1 2 2 2 3 2 6 1 2 3 1 2 3 -1 6 1 1 1 2 2 2 1 2 3 3 2 3 3 2 2 1 -1