[ ZJOI 2006 ] Trouble
\(\\\)
\(Description\)
有\(N\)个人的环,每个人需要至少\(x_i\)种不同的物品,并且要求任意相邻的两人都没有相同的物品,求最少需要多少种物品。
- \(N\in [0,2\times 10^4]\),\(x_i\in [0,10^5]\)
\(\\\)
\(Solution\ \text O(NlogN)\)
考虑二分答案,首先注意到相邻两人所有物品种类一定不同,所以下界是相邻两人限制之和取\(max\)。
注意到限制只是两两之间的,如果是奇环的话只有头尾会出问题,所以上界最多只需要下界的二倍。
验证的部分就很神仙了,思想是\(min-max\)转化:
设\(mx[i]\)表示在二分总个数为\(x\)的情况下,第\(i\)个位置的人所得物品中,与第一个人相同的个最多有多少个,同理设\(mn[i]\)表示此情况下第\(i\)个位置的人与第一个人最少有多少个相同的物品。
最大部分的转移:考虑要求与前一个不同,所以从第一个人得到的所有物品里去掉前一个最少得到的即可\(\begin{align}mx[i]=min(x[i],x[1]-mn[i-1])\end{align}\)
最小部分的转移:所求即为第一个人得到的所有物品里,去掉当前人最多能够不与第一个人重合的部分,但是还要考虑两人不能重合,所以有\(\begin{align}mn[i]=max(0,a[i]-(x-(a[i-1]-mx[i-1])-a[1]))\end{align}\)具体可以理解成自由部分即为全集去掉第一个人的所有和前一个人的所有,再减掉两个人可行的最大交集。
若最后一个人的最小值可以为\(0\)则证明不会与第一个人冲突,合法。
\(\\\)
\(Code\)
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 20010
#define R register
#define gc getchar
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
int n,l,r,a[N],mx[N],mn[N];
inline bool valid(int x){
mn[1]=mx[1]=a[1];
for(R int i=2;i<=n;++i){
mx[i]=min(a[i],a[1]-mn[i-1]);
mn[i]=max(0,a[i]-(x-(a[i-1]-mx[i-1])-a[1]));
}
return (mn[n]==0);
}
int main(){
n=rd();
for(R int i=1;i<=n;++i) a[i]=rd();
l=a[n]+a[1];
for(R int i=1;i<n;++i) l=max(l,a[i]+a[i+1]);
r=l*2;
while(l<r){
int mid=(l+r)>>1;
valid(mid)?r=mid:l=mid+1;
}
printf("%d\n",l);
return 0;
}
\(\\\)
\(Solution\ \text O(N)\)
这题还有更神仙的做法
首先必须考虑的限制不变,还是两两相邻求和最大值。
考虑另外的限制,即出现奇环时问题的解决方案,此时神仙们怎么就能想到另外一个切入点,每个相同的物品至多只能分给\(\lfloor\frac{N}{2}\rfloor\)个人,因为再多一个人必然会出现相邻的冲突。那么假设\(sum=\sum x_i\),那么\(sum\)这么多的物品中每一类最多只能有\(\lfloor\frac{N}{2}\rfloor\)个有贡献,所以只考虑总和的情况下,至少需要\(\Big\lceil\frac{sum}{\big\lfloor\frac{N}{2}\big\rfloor}\Big\rceil\)种。
对两个角度的答案取最大即可。
\(\\\)
\(Code\)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 20010
#define R register
#define gc getchar
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
int n,ans,sum,a[N];
int main(){
n=rd();
for(R int i=1;i<=n;++i) sum+=(a[i]=rd());
ans=max(a[n]+a[1],(int)ceil((double)sum/(n/2)));
for(R int i=1;i<n;++i) ans=max(ans,a[i]+a[i+1]);
printf("%d\n",ans);
return 0;
}
最新文章
- ubuntu安装谷歌输入法
- Win8 安装 Scrapy
- Android闹钟 AlarmManager的使用
- 一种高效的 vector 四则运算处理方法
- KVM背靠Linux好乘凉
- PAT-乙级-1003. 我要通过!(20)
- lnmp 虚拟主机配置及重写
- VS2015 Cordova Ionic移动开发(三)
- Cordova VS React Native 谁是未来? - b
- IoC容器Autofac正篇之解析获取(六)
- kafka 0.10.2 消息生产者
- 在App Store中无法更新xcode 8.3.2时 以及更新新系统10.12
- Zepto源码分析之一(代码结构及初始化)
- 错误RSA host key for [ip address] has changed and you have requested strict checking.
- Unity5权威讲解+项目源码+MP4
- linux 串口驱动(二)初始化 【转】
- Zabbix之Python发送邮件
- win10拖拽的问题
- Python: 在序列上执行聚集函数(比如sum() , min() , max() )
- Docker Macvlan
热门文章
- HDU 1254 条件过程复杂的寻找最短路
- node.js 发布订阅模式
- 模拟赛 Problem 3 经营与开发(exploit.cpp/c/pas)
- 20、Java并发性和多线程-Slipped Conditions
- RAR5格式不同词典大小下压缩率的简单测试
- SVM学习(续)核函数 &; 松弛变量和惩罚因子
- Reduce 任务的完整数据流
- [Vue @Component] Pass Props Between Components with Vue Slot Scope &; renderless component
- 查看程序占用tomcat内存情况
- ocpm