读数消融判定蔚来技术岗 8月17号笔试 第一题题目内容产线侧在工位上部署了测点回传一条长度为n nn的整型读数序列{ v 1 , v 2 , … , v n } \{v_1,v_2,\dots,v_n\}{v1​,v2​,…,vn​}。质检模块每次可任选两个不同下标p , q p,qp,qp ≠ q p\neq qpq若∣ v p − v q ∣ ≤ 1 |v_p-v_q|\le 1∣vp​−vq​∣≤1即两读数相等或恰相差1 11则抹去其中较大的那条两读数相等时任抹其一。请判断能否经过若干次上述抹除使序列最终只剩一条读数。输入描述第一行一个整型k kk1 ≤ k ≤ 1000 1 \le k \le 10001≤k≤1000表示随后有k kk条读数序列。对其中每一条序列第一行一个整型n nn2 ≤ n ≤ 1200 2 \le n \le 12002≤n≤1200表示该序列长度。第二行n nn个正整型v 1 , v 2 , … , v n v_1, v_2, \dots, v_nv1​,v2​,…,vn​1 ≤ v i ≤ 250 1 \le v_i \le 2501≤vi​≤250表示各测点读数。请对每条序列逐一判定能否消融到只剩一条读数。输出描述共写出k kk行。对每一条序列若可以消融到只剩一条读数写出YES否则写出NO。示例 1输入3 3 2 3 4 2 5 7 6 1 2 2 3 3 4输出YES NO YES说明第一条{ 2 , 3 , 4 } \{2,3,4\}{2,3,4}选3 33与4 44抹去4 44再选2 22与3 33抹去3 33剩2 22。第二条{ 5 , 7 } \{5,7\}{5,7}∣ 5 − 7 ∣ 2 |5-7|2∣5−7∣2无法操作不能消到一条。第三条{ 1 , 2 , 2 , 3 , 3 , 4 } \{1,2,2,3,3,4\}{1,2,2,3,3,4}可先抹去4 44与某个3 33配对再抹去两个3 33分别与2 22配对再抹去多余的2 22与1 11配对最后剩1 11。示例 2输入2 4 8 8 10 9 3 1 1 3输出YES NO说明第一条选10 1010与9 99抹去10 1010得到{ 8 , 8 , 9 } \{8,8,9\}{8,8,9}再选9 99与某个8 88抹去9 99得到{ 8 , 8 } \{8,8\}{8,8}再抹去其中一个8 88剩8 88。第二条只能把两个1 11配成一对并抹去其中一个得到{ 1 , 3 } \{1,3\}{1,3}此时∣ 1 − 3 ∣ 2 |1-3|2∣1−3∣2无法继续最终剩两条。题解和思路思路实现思路模拟题目可以直接忽略每个数出现次数只需要考虑数是否出现因为两读数相等时任抹其一, 通过组合可以达到每个数只出现一次。所以采用flag数组存储每个[1, 250]每个数是否出现。然后从后往前遍历当flag[i] true时判断flag[i-1]是否存在不存在的话不能消除数量 1.最终判断不能消除数量是否小于等于1. 满足输出YES反之输出NO算法平均时间复杂度为O(nk)C#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intk;cink;while(k--){// 标记指定数是否出现vectorboolflag(251,false);intn;cinn;for(inti0;in;i){intx;cinx;flag[x]true;}inttotal0;for(inti250;i1;i--){if(!flag[i]){continue;}// 不能被消除if(i-10||!flag[i-1]){total;}}cout(total1?YES:NO)endl;}return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringBuilderoutnewStringBuilder();intkInteger.parseInt(br.readLine().trim());while(k--0){// 标记指定数是否出现boolean[]flagnewboolean[251];intnInteger.parseInt(br.readLine().trim());StringTokenizerstnewStringTokenizer(br.readLine());for(inti0;in;i){intxInteger.parseInt(st.nextToken());flag[x]true;}inttotal0;for(inti250;i1;i--){if(!flag[i]){continue;}// 不能被消除if(i-10||!flag[i-1]){total;}}out.append(total1?YES:NO).append(\n);}System.out.print(out);}}pythonimportsys datalist(map(int,sys.stdin.buffer.read().split()))idx0kdata[idx]idx1ans[]whilek0:k-1# 标记指定数是否出现flag[False]*251ndata[idx]idx1foriinrange(n):xdata[idx]idx1flag[x]Truetotal0foriinrange(250,0,-1):ifnotflag[i]:continue# 不能被消除ifi-10ornotflag[i-1]:total1ans.append(YESiftotal1elseNO)sys.stdout.write(\n.join(ans))Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,(line){lines.push(line.trim());});rl.on(close,(){letlineIndex0;constkNumber(lines[lineIndex]);constans[];for(lett0;tk;t){// 标记指定数是否出现constflagnewArray(251).fill(false);constnNumber(lines[lineIndex]);constvalueslines[lineIndex].split(/\s/).map(Number);for(leti0;in;i){constxvalues[i];flag[x]true;}lettotal0;for(leti250;i1;i--){if(!flag[i]){continue;}// 不能被消除if(i-10||!flag[i-1]){total;}}ans.push(total1?YES:NO);}console.log(ans.join(\n));});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varkintfmt.Fscan(in,k)for;k0;k--{// 标记指定数是否出现flag:make([]bool,251)varnintfmt.Fscan(in,n)fori:0;in;i{varxintfmt.Fscan(in,x)flag[x]true}total:0fori:250;i1;i--{if!flag[i]{continue}// 不能被消除ifi-10||!flag[i-1]{total}}iftotal1{fmt.Fprintln(out,YES)}else{fmt.Fprintln(out,NO)}}}