题解【CF1303D Fill The Bag】
\]
不开 long long 见祖宗。
\]
你有一个 \(n\) 码的袋子,你还有 \(m\) 个盒子,第 \(i\) 个盒子的尺寸是 \(a_i\) ,这里的每一个 \(a_i\) 都是 \(2\) 的非负幂整数。
你可以把盒子分成大小相等的两部分。你的目标是完全装满袋子。
例如 \(n=10,a=[1,1,32]\) ,那么你必须把 \(32\) 码的盒子分成 \(16\) 码的两部分,然后把 \(16\) 码的盒子分开,你可以用 \(1\) 码,\(1\) 码,\(8\) 码的盒子装满袋子。
计算填充尺寸为 \(n\) 的袋子所需的最小分割数。
**多组数据,无解输出 -1
。 **
\]
先来讨论一下 -1
的情况:
考虑到分裂一个数不会影响到所有数的和。
那么我们将所有数都分裂成 \(1\) ,由于和不变,此时 \(1\) 的个数为 \(\sum\limits_{i=1}\limits^{m}a[i]\) ,也就是说小于等于 \(\sum\limits_{i=1}\limits^{m}a[i]\) 的数都可以被填出来。
故当 \(n>\sum\limits_{i=1}\limits^{m}a[i]\) 时,无解。
\(~\)
有一个看起来很正确的贪心策略:
将 \(n\) 二进制拆分成 \(2^{k_1},2^{k_2},...,2^{k_c}\) 。
然后从低位(\(2^{k_1}\))到高位(\(2^{k_c}\))贪心填数。
假设我们当前处理到的数为 \(2^{k_i}\) 。
首先考虑位数小于等于 \(k_i\) 的所有数中,能不能凑成 \(2^{k_i}\) ,若可以,直接填上去;否则考虑分裂位数大于 \(k_i\) 的所有数中最小的那一个,使其经过若干次分裂,分裂成 \(2^{k_i}\) 。
详情见 \(\texttt{Code}\) 。
\]
#include<cstdio>
#include<cstring>
#define RI register int
using namespace std;
const int N=100100;
int T;
long long n; int m;
int a[N];
long long ans,sum;
long long cnt[65]; // cnt[k] : 2^k 的出现次数
long long calc(int k) // 计算小于等于 k 的位数中可以组成多少个 2^k
{
long long ans=0;
for(RI i=0;i<k;i++)
ans=(ans+cnt[i])/2;
return ans+cnt[k];
}
void work()
{
memset(cnt,0,sizeof(cnt));
ans=sum=0;
scanf("%lld%d",&n,&m);
for(RI i=1;i<=m;i++)
scanf("%d",&a[i]),sum+=a[i];
if(n>sum)
{
puts("-1");
return;
}
for(RI i=1;i<=m;i++)
for(RI j=0;j<=31;j++)
if((a[i]>>j)&1)
{
cnt[j]++;
break;
}
for(RI k=0;k<=63;k++)
{
if(((n>>k)&1)==0)continue; // 如果 n 的第 k 位为 0 就 continue
if(calc(k)) // 情况 1
cnt[k]--; // 理论上应该要让组成 2^k 的那些数减 , 但实际上这样做 , 在 calc 里也是正确的
else // 情况 2
{
for(RI p=k+1;p<=63;p++) // 找到位数大于 k 的数中最小的那个
if(cnt[p])
{
cnt[p]--; // 模拟分裂
for(RI i=k;i<p;i++)
cnt[i]++; // 模拟分裂
ans+=p-k; // 统计答案
break;
}
}
}
printf("%lld\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--) work();
return 0;
}
\]
最新文章
- 使用RequireJs和Bootstrap模态框实现表单提交
- Ubuntu 下安装 MySQL Workbench
- [Nginx] - PHP+FPM相关的配置
- (原创)mybatis学习四,利用mybatis自动创建代码
- lunix机器的jdk安装
- Java 动态生成 复杂 .doc文件
- JDBC注册驱动
- 初学者:浅谈web前端就业的学习路线
- Linux指令--watch,at
- php7 curl返回false error返回空串
- mysql初始化提示安装perl
- linux-shell系列5-统计
- DotNet 资源大全中文版
- 操作系统中的IPC机制(inter-process Communication)
- Steam API调试
- 一步步Cobol 400上手自学入门教程06 - 子程序调用
- HGOI20180815 (NOIP 提高组模拟赛 day2)
- 【Unity】4.6 灯光
- metabase docker-compose 运行说明
- Linux笔记:vi常用命令