CF 1278C Berry Jam 题解
2024-09-01 23:12:17
Forewords
说实话我是被图吸引进来的23333,图画的真的挺好看。
题意
你从一个梯子下到地下室,梯子左右两边各有 \(n\) 瓶果酱排成一排,果酱口味为草莓味或蓝莓味,你每次只能吃你左边或右边没吃过的那瓶,求最少要吃多少瓶才能使两种口味的果酱数量相等。
题解
以样例为例,有 \(7\) 罐草莓味的和 \(5\) 罐蓝莓味的。
然后一直往右边吃,吃到这个时候,吃掉了 \(3\) 草蓝莓味的和 \(2\) 罐蓝莓味的,剩下 \(r_\text{left}=4\) 罐草莓味的和 \(b_\text{left}=3\) 罐蓝莓味的。
这时候,为了达到目的,可以再吃 \(r\) 罐草莓味的和 \(b\) 罐蓝莓味的,可行方案如下表:
\(r\) | \(b\) |
---|---|
\(1\) | \(0\) |
\(2\) | \(1\) |
\(3\) | \(2\) |
\(\dots\) | \(\dots\) |
可以发现,\(r-b\) 保持不变,且等于 \(r_\text{left}-b_\text{left}\)。
这一结论很显然,因为 \(r\) 和 \(b\) 只能减,不能增,因此达到目标的最好方法就是把数量多的口味吃到和另一个口味数量相等。然而这个方案并不一定能够达到,因此在这个的基础上再两种口味同时多吃 \(v\) 瓶。
具体实现就是预处理单吃一侧不同数量时产生的差值,然后枚举吃另一侧 \(1\dots n\) 瓶时要在另一侧吃的差值对应去找即可。
注意处理一下边界。
Code
这里因为带了个 map 所以复杂度是 \(O(n\log n)\),但是 map 可以优化成数组,降到 \(O(n)\)(比官方给的题解少一个 \(\log\))。
运用了一些小技巧来对调两边(其实可能不需要)。
#include<cstdio>
#include<map>
const int MAXN=1e5+5;
int a[MAXN],b[MAXN],t,bflag[MAXN],n,gtotr,gtotb,ans;
std::map<int,int>map;
int main()
{
scanf("%d",&t);
t*=2;
int cur=0;
for(;t>=1;t--)
{
map.clear();gtotr=gtotb=0;
if((++cur)%2)
{
ans=2147483647;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
}
else
{
for(int i=1;i<=n;i++)
std::swap(a[i],b[n-i+1]);
/*
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
for(int i=1;i<=n;i++)
printf("%d ",b[i]);
printf("\n");
*/
}
for(int i=1;i<=n;i++)
{
if(a[i]==1) gtotr++; else gtotb++;
}
int totr=0,totb=0;
map[0]=-1;
for(int i=1;i<=n;i++)
{
if(b[i]==1) totr++; else totb++;
bflag[i]=totr-totb;
if(!map[bflag[i]]) map[bflag[i]]=i;
// printf("%d %d\n",bflag[i],i);
}
gtotr+=totr;gtotb+=totb;
if(gtotr==gtotb) {if(!(cur%2))printf("0\n");continue;}
totr=totb=0;
for(int i=n;i>=1;i--)
{
if(a[i]==1) totr++; else totb++;
int result=map[(gtotr-totr)-(gtotb-totb)];
// printf("Eat [%d %d], Left[%d %d], Result %d\n",totr,totb,gtotr-totr,gtotb-totb,(gtotr-totr)-(gtotb-totb));
if(result) {if(result<0) result=0;ans=std::min(ans,n-i+1+result);}
}
if(!(cur%2)) printf("%d\n",ans);
}
return 0;
}
最新文章
- ZKWeb网页框架1.1正式发布
- jstl 标签库的使用
- Linux配置网络YUM源
- 查找代码错误.java
- Mybatis 开启事务@Transactional
- TCP/IP详解学习笔记(13)-- TCP连接的建立与终止
- WPF的依赖属性
- STUN/TURN/ICE协议在P2P SIP中的应用(二)
- 老李回答:JAVA程序的性能测试方法
- C++构造函数初始化列表与赋值
- 深入理解计算机系统chapter6
- centos 安装nvm和node.js
- 用grunt对css代码进行压缩
- CF 958E2. Guard Duty (medium)
- Mybatis学习2传统dao开发
- 短时傅里叶变换(Short Time Fourier Transform)原理及 Python 实现
- 20162328蔡文琛 大二 十二周课上测试 hash
- 使用html2canvas实现超出浏览器部分截图
- ORA-39006、ORA-39065、ORA-01403、ORA-39097错误解决办法
- C语言命令行处理