Codeforces 626C Block Towers「贪心」「二分」「数学规律」

题意:

一堆人用方块盖塔,有n个人每次只能加两块方块,有m个人每次只能加三块方块。要求每个人盖的塔的高度都不一样,保证所用方块数最少,求最高的塔的高度。

0<=n+m  0<=n,m<=1e6

思路:

根据容斥原理,n和m个人如果都按照等差为2或者3的序列盖塔的话那么重复的个数应该是塔高较小的那组除以6,然后....一开始顺着这个思路想把自己坑了...

其实可能的塔高是有规律的 2 3 4 6 8 9 10 12...每六个中有三个,所以干脆先打表了,那么知道n和m之后,至少需要n+m种塔高。然后二分需要塔高的数目使得最高的塔高同时满足两种需要。

#include<bits/stdc++.h>
using namespace std;
int biao[];
int bSearch(int l,int r,int n,int m){
int mid;
while(l<=r){
mid=(l+r)>>;
if(biao[mid]/>=n&&biao[mid]/>=m){
r=mid-;
}
else{
l=mid+;
}
}
return l;
}
int main()
{
for(int i=;i<=;i++){
biao[i]=(i-)/*;
if(i%==)biao[i]+=;
else if(i%==)biao[i]+=;
else if(i%==)biao[i]+=;
else biao[i]+=;
}
int n,m;
cin>>n>>m;
cout<<biao[bSearch(n+m,,n,m)];
}
上一篇:c/c++的Soap应用


下一篇:Linux架构之NFS共享存储1