企业官网建设流程全解析

本文涉及知识点

数学

[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_iai​by1 11.
• Choose a tower and decrease its heighta i a_iai​by1 11.
• Choose a tower and divide its heighta i a_iai​by2 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≤m<n), 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

样例输入 #1

3 2 0 2 6 5 0 1 2 3 4 5 5 3 1 2 3 4 5

样例输出 #1

2 4 1

数学

f(x) 将任意N-M的塔的高度改成x的最小成本。m = max(a)。
性质一：存在最优解，除2之前没有加减法。（x+1)/2和(x-1)/2和x/2相等或相差1。如果相差1，除以2之后，再加减，是不劣解。如果相等，移到除2外，是更优解。
性质二：x除2 i1次后，是x1，x2=x1/2。则任意x3∈ \in∈[x1,x2]$的最优解是： min(i1+x3-x1,i1+1+x2-x3)。
性质三：i1+x3-x1 <= i1+1+x2-x3⟺ \iff⟺2x3 <= 1+x2+x1
x4 = 1+x1+x2，如果x4是偶数：
x <= x4/2 ，i1+x3-x1 是更优解；否则i1+1+x2-x3 是更优解。
如果x4是奇数：也是如此。
推论一：x∈ \in∈[x1,x4/2]， x++,则f(x)也加1。x∈ \in∈[x4/x+1,x3]。x++，则f(x)减1。
我们将所有的x1,x2,x4/2,x4/2+1放到有序集合s中。x5,x6是s中任意两个相邻元素，x5<x6。
结论一：任意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)

代码

核心代码

#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<cstring>#include<list>#include<bitset>usingnamespacestd;template<classT1,classT2>std::istream&operator>>(std::istream&in,pair<T1,T2>&pr){in>>pr.first>>pr.second;returnin;}template<classT1,classT2,classT3>std::istream&operator>>(std::istream&in,tuple<T1,T2,T3>&t){in>>get<0>(t)>>get<1>(t)>>get<2>(t);returnin;}template<classT1,classT2,classT3,classT4>std::istream&operator>>(std::istream&in,tuple<T1,T2,T3,T4>&t){in>>get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);returnin;}template<classT=int>vector<T>Read(){intn;scanf("%d",&n);vector<T>ret(n);for(inti=0;i<n;i++){cin>>ret[i];}returnret;}template<classT=int>vector<T>Read(intn){vector<T>ret(n);for(inti=0;i<n;i++){cin>>ret[i];}returnret;}classSolution{public:longlongAns(vector<int>&a,constintM){constintN=a.size();set<int>s;s.emplace(0);vector<vector<pair<int,int>>>b;for(autoi:a){vector<int>tmp;while(i){tmp.emplace_back(i);intx4=i+(i/2)+1;s.emplace(x4/2);s.emplace(x4/2+1);s.emplace(i);i/=2;}tmp.emplace_back(0);b.emplace_back();for(intj=tmp.size()-1;j>=0;j--){b.back().emplace_back(tmp[j],j);}}longlongans=LLONG_MAX/2;for(autoit=s.rbegin();it!=s.rend();++it){constinttarget=*it;vector<int>cur;for(intj=0;j<N;j++){auto&v=b[j];while((v.size()>=2)&&(v[v.size()-2].first>=target)){v.pop_back();}constinttmp1=abs(v.back().first-target)+v.back().second;inttmp2=INT_MAX/2;if(v.size()>=2){tmp2=abs(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());longlongcurAns=accumulate(cur.begin(),cur.begin()+N-M,0LL);ans=min(ans,curAns);}returnans;}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUGintT;cin>>T;for(inti=0;i<T;i++){intn,m;cin>>n>>m;autoa=Read<int>(n);autores=Solution().Ans(a,m);cout<<res<<endl;}#ifdef_DEBUG//printf("K=%d", K);//Out(b, "b=");//Out(strs, ",strs=");#endif// DEBUGreturn0;}

单元测试

vector<int>a;intM;TEST_METHOD(TestMethod11){a={2,6},M=0;autores=Solution().Ans(a,M);AssertEx(2LL,res);}TEST_METHOD(TestMethod12){a={1,2,3,4,5},M=0;autores=Solution().Ans(a,M);AssertEx(4LL,res);}TEST_METHOD(TestMethod13){a={1,2,3,4,5},M=3;autores=Solution().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); }