本文涉及知识点数学[ICPC2022 Jinan R] Tower题面翻译题目描述庞教授搭了n nn座不同高度的塔。第i ii座塔的高度是a i a _ {i}ai。寿教授不喜欢这些参差不齐的塔。他决定先去掉它们中的m mm座然后执行以下操作中的一些或不执行选择一座塔并增加它1 11个单位高度。选择一座塔并减少它1 11个单位高度。选择一座塔并把它的高度a i a _ {i}ai除以2 22如果它不是整数的话向下取整。寿教授永远不会选择被拆除的塔。如果操作后塔的高度变为0 00则不允许操作。在这些约束条件下寿教授可以按任意顺序执行任意数量的运算。寿教授希望所有没有被拆除的塔都有相同的高度a i a _ {i}ai。请计算实现此目标的最小操作次数。输入格式第一行是一个整数T ( 1 ⩽ T(1\leqslantT(1⩽T TT⩽ \leqslant⩽10 ) 10)10),表示有T TT组数据。对于每组测试数据第一行包括两个整数n , m ( 1 ⩽ n,m (1\leqslantn,m(1⩽n nn⩽ \leqslant⩽500 500500, ,,0 00⩽ \leqslant⩽m mm⩽ \leqslant⩽n nn) ))表示塔的数量以及寿教授在执行操作之前应该删除的塔的数量。下一行包括n nn个整数a 1 , … , a n ( 1 ⩽ a _ {1},\dots,a _ {n} (1\leqslanta1,…,an(1⩽a i a _ {i}ai⩽ \leqslant⩽10 9 ) 10^9)109)表示塔的最初高度。输出格式对于每组测试数据在一行中输出最小操作数。题目描述Prof. Pang builtn nnblock towers with different heights. Thei ii-th tower has heighta i a_iai.Prof. Shou doesn’t like these towers because of their arbitrary heights. He decides tofirst remove exactly m of them \textbf{first remove exactly \textit{m} of them}first remove exactlymof them, and then perform some (or none) of the following operations:Choose a tower and increase its heighta i a_iaiby1 11.Choose a tower and decrease its heighta i a_iaiby1 11.Choose a tower and divide its heighta i a_iaiby2 22. If the new height is not an integer, it is rounded down.Prof. Shou can never choose a removed tower. If after an operation, the height of a tower will become0 00, that operation is not allowed. Under these constraints, Prof. Shou can perform an arbitrary number of operations in arbitrary order.Prof. Shou would like all the towers that are not removed to have the same heights. Please calculate the minimum number of operations to achieve this.输入格式The first line contains one integerT ( 1 ≤ T ≤ 10 ) T~(1\le T \le 10)T(1≤T≤10), the number of test cases.For each test case, the first line contains two integersn , m ( 1 ≤ n ≤ 500 , 0 ≤ m n ) n, m~(1\le n\le 500, 0\le m n)n,m(1≤n≤500,0≤mn), the number of towers, and the number of towers Prof. Shou should delete before performing the operations.The next line containsn nnintegersa 1 , … , a n ( 1 ≤ a i ≤ 10 9 ) a_1,\ldots, a_n~(1\le a_i\le 10^9)a1,…,an(1≤ai≤109), the initial heights of the towers.输出格式For each test case, output the minimum number of operations in one line.样例 #1样例输入 #13 2 0 2 6 5 0 1 2 3 4 5 5 3 1 2 3 4 5样例输出 #12 4 1数学f(x) 将任意N-M的塔的高度改成x的最小成本。m max(a)。性质一存在最优解除2之前没有加减法。x1)/2和(x-1)/2和x/2相等或相差1。如果相差1除以2之后再加减是不劣解。如果相等移到除2外是更优解。性质二x除2 i1次后是x1x2x1/2。则任意x3∈ \in∈[x1,x2]$的最优解是 min(i1x3-x1,i11x2-x3)。性质三i1x3-x1 i11x2-x3⟺ \iff⟺2x3 1x2x1x4 1x1x2如果x4是偶数x x4/2 i1x3-x1 是更优解否则i11x2-x3 是更优解。如果x4是奇数也是如此。推论一x∈ \in∈[x1,x4/2] x,则f(x)也加1。x∈ \in∈[x4/x1,x3]。x则f(x)减1。我们将所有的x1,x2,x4/2,x4/21放到有序集合s中。x5,x6是s中任意两个相邻元素x5x6。结论一任意x∈ \in∈[x5,x6]。f(x) min(f(x5),f(x6))。证明根据推论一任意塔在[x5,x6]要么递增要么递减。如果递增的数量大于等于抵减的数量则f(x5)是区间最优解。否则f(x6)是区间最优解。如果最终高度在[0,M]则结果一定在s中。如果最终高度 M则劣于M。结论只需要枚举s中的高度数量nlog(M)。时间复杂度O(Tnlog(M)(nlogM))在超时的边缘f(x)利用缓存要少量优化空间。本题超时时间是6s而不是1秒。优化最小的N-M个f(j,i)不用排序直接用nth。b[i]记录a[i] ,a[i]/2 ,a[i]/4⋯ \cdots⋯降序。通过target从大到小枚举s如果b[i][v.size()-2]大于 target b[i].pop_back()时间复杂度O(Tnlog(M)n)代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#includelist#includebitsetusingnamespacestd;templateclassT1,classT2std::istreamoperator(std::istreamin,pairT1,T2pr){inpr.firstpr.second;returnin;}templateclassT1,classT2,classT3std::istreamoperator(std::istreamin,tupleT1,T2,T3t){inget0(t)get1(t)get2(t);returnin;}templateclassT1,classT2,classT3,classT4std::istreamoperator(std::istreamin,tupleT1,T2,T3,T4t){inget0(t)get1(t)get2(t)get3(t);returnin;}templateclassTintvectorTRead(){intn;scanf(%d,n);vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}classSolution{public:longlongAns(vectorinta,constintM){constintNa.size();setints;s.emplace(0);vectorvectorpairint,intb;for(autoi:a){vectorinttmp;while(i){tmp.emplace_back(i);intx4i(i/2)1;s.emplace(x4/2);s.emplace(x4/21);s.emplace(i);i/2;}tmp.emplace_back(0);b.emplace_back();for(intjtmp.size()-1;j0;j--){b.back().emplace_back(tmp[j],j);}}longlongansLLONG_MAX/2;for(autoits.rbegin();it!s.rend();it){constinttarget*it;vectorintcur;for(intj0;jN;j){autovb[j];while((v.size()2)(v[v.size()-2].firsttarget)){v.pop_back();}constinttmp1abs(v.back().first-target)v.back().second;inttmp2INT_MAX/2;if(v.size()2){tmp2abs(v[v.size()-2].first-target)v[v.size()-2].second;}cur.emplace_back(min(tmp1,tmp2));}nth_element(cur.begin(),cur.begin()N-M-1,cur.end());longlongcurAnsaccumulate(cur.begin(),cur.begin()N-M,0LL);ansmin(ans,curAns);}returnans;}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGintT;cinT;for(inti0;iT;i){intn,m;cinnm;autoaReadint(n);autoresSolution().Ans(a,m);coutresendl;}#ifdef_DEBUG//printf(K%d, K);//Out(b, b);//Out(strs, ,strs);#endif// DEBUGreturn0;}单元测试vectorinta;intM;TEST_METHOD(TestMethod11){a{2,6},M0;autoresSolution().Ans(a,M);AssertEx(2LL,res);}TEST_METHOD(TestMethod12){a{1,2,3,4,5},M0;autoresSolution().Ans(a,M);AssertEx(4LL,res);}TEST_METHOD(TestMethod13){a{1,2,3,4,5},M3;autoresSolution().Ans(a,M);AssertEx(1LL,res);}} TEST_METHOD(TestMethod13) { a { 1,2,3,4,5 }, M 3; auto res Solution().Ans(a, M); AssertEx(1LL, res); }