2016 ACM-ICPC 青岛站网络赛G题 题解
2024-08-28 22:07:01
【参考博客】【https://blog.csdn.net/Tawn0000/article/details/82255682】
题意:
将n个数按照每k个一组来合并,合并需要花费的cost是两个数的长度和,问:在T的消费内将所有的数合并所需的最小的k。
分析:
合并之前要处理一下零头,因为每次取k个一直到最后一步剩下的数的个数可能会少于k个,这样的结果就是合并的cost更大了,举个例子:1 2 3 4 5 6,k=4时,先选1 2 3 4然后再5 6 10 是31,但是因为零头有3,先处理3个零头,即:先取1 2 3然后是4 5 6 6 ,是27。显然27<31。
和被参考的那边博主一样,我也是一开始按照二分+优先队列的思路来进行考虑的,最后在O(n logn logn)的复杂度下TLE了。
如果采用双队列(一个队列存原来的数(从小到大排序后再入队),记为队列p1,另一个队列存合并后的数,记为队列p2),时间复杂度是O(n logn)。
双队列具体操作是取p1中k个原来的数相加,加完之后的值和p2队列取出的值数比较,取小的数加入p2(记得pop掉被取队列中的数),因为原队列的数按照从小到大的顺序排列的,所以一定会满足先入队的数比后入队的数小!。这样一来就会使得参与合并的数总是从小的开始。
AC code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
queue<int> q1,q2;
int a[];
int n,T;
bool P(int mid)
{
while(q1.size()) q1.pop();
while(q2.size()) q2.pop();
for(int i=;i<n;i++) q1.push(a[i]);
ll res=;
int t=(n-)%(mid-);
if(t)
{
int p=;
for(int i=;i<t+&&!q1.empty();i++)
{
p+=q1.front();
q1.pop();
}
res+=p;
q2.push(p);
}
while()
{
int p=;
for(int i=;i<mid;i++)
{
int x=,y=;
if(q1.empty()&&q2.empty()) break;
if(!q1.empty()) x=q1.front();
if(!q2.empty()) y=q2.front();
if(x<y)
{
p+=x;
q1.pop();
}
else
{
p+=y;
q2.pop();
}
}
res+=p;
if(res>T) return true;
if(q1.empty()&&q2.empty()) break;
q2.push(p);
}
if(res>T) return true;
else return false;
}
int main()
{
//freopen("input.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&T);
for(int i=;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
int sd=,ed=n;
while(ed - sd > )
{
int mid=sd+(ed-sd)/;
if(P(mid)) sd=mid;
else ed=mid;
}
printf("%d\n",ed);
}
}
最新文章
- 一个简单的网站web项目的详解
- 三代PacBio reads纠错 - 专题
- Java中流的概念
- 显示hello
- jquery.fileupload插件的简易使用日志
- TCP报头
- BASE64编码规则及C#实现
- phpcms首页商机的调用,多种方式
- 不可综合的verilog语句分析
- jQuery验证插件
- Dynamics CRM 2011/2013 section的隐藏
- 苹果新的编程语言 Swift 语言进阶(四)--字符串和收集类型
- SVN安装后bin中没有svn.exe,TortoiseSVN安装后bin目录中没有svn.exe;
- WCF简单实例--用Winform启动和引用
- 并发系列(三)-----volatile
- CF475C. Kamal-ol-molk&#39;s Painting
- java.lang.NoSuchMethodException:com.yxq.action.AdminAction.addGoods()《转载》
- Redis学习篇(九)之生存时间
- 树莓派/RaspberryPi 内核源码下载
- Renderer.materials 和sharedMaterials一些用法上的区别