首页 > 代码库 > hdu_5884_Sort(二分+单调队列)
hdu_5884_Sort(二分+单调队列)
题目链接：hdu_5884_Sort
题意：
有n个数，每个数有个值，现在你可以选择每次K个数合并，合并的消耗为这K个数的权值和，问在合并为只有1个数的时候，总消耗不超过T的情况下，最小的K是多少
题解：
首先要选满足条件的最小K，肯定会想到二分。
然后是如何来写这个check函数的问题
我们要贪心做到使消耗最小，首先我们将所有的数排序
然后对于每次的check的mid都取最小的mid个数来合并，然后把新产生的数扔进优先队列，直到最后只剩一个数。
不过这样的做法是n*(logn)2 ,常数写的小，带优化能卡过去，不过我反正卡不过去，然后就需要一个数据结构优化一个log
那就是用单调队列，可以先看看这篇文章 合并果子
然而这里有个小细节，不注意是过不去的：
对于n个数，一共要合并n-1个数，才能最后剩一个数，然后对于每次的mid,每次会合并mid-1个数，如果(n-1)%(mid-1)!=0,那么我们得先取(n-1)%(mid-1)+1个数来合并，这样后面合并的时候才能刚合适，如果不取，读者可以自己模拟一下，会出错。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 typedef long long ll; 5 6 const int N=1e5+7; 7 int t,n,T,a[N]; 8 ll inf=1e18; 9 queue<ll>Q1,Q2;10 11 bool check(int mid)12 {13 ll ans=0;14 while(!Q1.empty())Q1.pop();15 while(!Q2.empty())Q2.pop();16 F(i,1,n)Q1.push(a[i]);17 int num=(n-1)%(mid-1);18 if(num)19 {20 ll tp=0;21 F(i,1,num+1)tp+=Q1.front(),Q1.pop();22 ans+=tp;23 Q2.push(tp);24 }25 while(1)26 {27 ll tp=0;28 F(i,1,mid)29 {30 ll x=inf,y=inf;31 if(Q1.empty()&&Q2.empty())break;32 if(!Q1.empty())x=Q1.front();33 if(!Q2.empty())y=Q2.front();34 if(x<y)tp+=x,Q1.pop();35 else tp+=y,Q2.pop();36 }37 ans+=tp;38 if(ans>T)return 0;39 if(Q1.empty()&&Q2.empty())break;40 Q2.push(tp);41 }42 return ans<=T;43 }44 45 46 int main(){47 scanf("%d",&t);48 while(t--)49 {50 scanf("%d%d",&n,&T);51 F(i,1,n)scanf("%d",a+i);52 sort(a+1,a+1+n);53 int l=2,r=n,mid,ans;54 while(l<=r)mid=(l+r)>>1,check(mid)?r=mid-1,ans=mid:l=mid+1;55 printf("%d\n",ans);56 }57 return 0;58 }
hdu_5884_Sort(二分+单调队列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。