题目描述
有n个水桶，第i个水桶里面水的体积为Ai，你可以用1秒时间向一个桶里添加1体积的水。
有q次询问，每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。
对于一次询问如果有多种方案，则采用使最终pi个桶中水的体积最小的方案。
示例1
输入
复制
4,3,[1,2,3,4],[2,2,4]
输出
复制
[1,0,5]
说明
第一次：花费一秒变为 2 2 3 4第二次：已经存在两个水的体积一样的桶第三次：花费五秒从2 2 3 4变为4 4 4 4
思路：考察一次查询，让k个水桶水量一样
- 先将水桶水量升序排序
- 滑动窗口的方式，依次考察不同区间段，使得水量相等的时间
- 记录下最小的时间，以及区间端点
关键点：
常规思路，需要采取多重遍历，时间复杂度很高
注意到：前一次窗口花费时间为T 那么下一个窗口内所需时间为
- T+=(L-1)*(A[i]-A[i-1]) 即增加上由于窗口新加入的A[i]元素，使得整体均值提高，这部分需要增加时间 A[i]-A[i-1]
- T-=A[i-1]-A[0] 即减去由于窗口右移动，省去的时间开销 A[i-1]-A[0]
即一次遍历，即可获取使得k个达到相同值得最小时间
vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {// write code herevector<int> res;sort(a.begin(),a.end());//排序//滑动窗口for(int i=0;i<q;i++){int len=p[i];//滑动窗口的长度int index_j=0;//标记下标int time=a[len-1]*len;//最少时间for(int j=0;j<len;j++)time-=a[j];//获得差值int min=time;//最少时间for(int s=len;s<n;s++) //s为起始点{//每次滑动一次 需要累加上由于均值变大导致的增加量 同时减去开头元素的开销time+=(a[s]-a[s-1])*(len-1)-(a[s-1]-a[s-len]);if(time<min){min=time;index_j=s-len+1;} } //结束之后 按照最少时间方案调整桶 for(int s=index_j;s<index_j+len;s++)a[s]=a[index_j+len-1]; res.push_back(min);} return res; }