#JC0301. Angry Cows
利用二分，来查找距离值，通过判断该距离值是否能安排的下所有的牛来调整l和r。
int n,m,a[100005];
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>m;
F(i,1,n)
CI a[i];
sort(a+1,a+n+1);
int l=0,r=a[n]-a[1],mid;
while (l<=r)
{
mid=(r+l)/2;
int x=a[1]+mid,t=2,s=1;
while (t<=n)
{
if(a[t]>=x) x=a[t]+mid,s++;
t++;
}
if (s>=m) l=mid+1;
else r=mid-1;
}
CO l-1 L;
return 0;
}#JC0302. Best Cow Fences
利用二分，查找平均数，并判断是否存在长度不低于L的子串能达到该平均数平均数。l的初始之为-1e6，r的初始值为1e6。计算出中间值m后，将Ai中的每一个数减去m，大于平均值m的数结果为正，小于平均值m的数结果为负；然后再计算一个前缀和数组d，求最大的平均值，需要找到前缀和d中最少的一个和最大的值，并保证最大的值在最小的值右边，且相距大于L。
int n,ll,a[100005];
double b[100005],d[100005];
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>ll;
F(i,1,n)
CI a[i];
double l=-1e6,r=1e6,m;
while (r-l>1e-5)
{
m=(l+r)/2;
F(i,1,n)
b[i]=a[i]-m;
F(i,1,n)
d[i]=b[i]+d[i-1];
double minl=1e10,avg=-1e10;
F(i,ll,n)
{
minl=min(minl,d[i-ll]);
avg=max(avg,d[i]-minl);
}
if (avg>=0) l=m;
else r=m;
}
CO int(r*1000) L;
return 0;
}#JC0304. Chat Ban
利用二分，找到能发的后一条消息，l和r存储发信息的条数，如果m小于k，则用求和公式m*(m+1)/2算出发送的标签数，如果大于k，则用求和公式算出未发出的表情数，并用总数减去未发出的表情数，得到已发的表情数：k*k-(2*k-1-m)*(2*k-1-m+1)/2
LL t,k,x;
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI k>>x;
if (k*k<=x)
CO 2*k-1 L;
else
{
LL l=0,r=2*k-1;
while (l<r)
{
LL m=(l+r)/2;
LL s=0;
if (m<=k) s=m*(m+1)/2;
else s=k*k-(2*k-1-m)*(2*k-1-m+1)/2;
if (s>=x) r=m;
else l=m+1;
}
CO r L;
}
}
return 0;
}#JC0305. Cow Acrobats
利用贪心，先将数组按照w+s值排序，然后再求出前缀和并利用前缀和和求出危险值的最大值。
struct cow
{
LL w,s;
} a[50001];
LL n,ans=-0x3f3f3f,s[500001];
bool cmp(cow a,cow b)
{
return a.w+a.s>b.w+b.s;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n;
F(i,1,n)
CI a[i].w>>a[i].s;
sort(a+1,a+n+1,cmp);
F(i,1,n)
s[i]=s[i-1]+a[i].w;
F(i,1,n)
{
LL t=s[n]-s[i];
t=t-a[i].s;
ans=max(ans,t);
}
CO ans L;
return 0;
}#JC0306. Fly
最节省的方法便是最后着陆后用完全部的燃料，于是可以倒求出着陆需要的燃料值，不断倒求出燃料值，得到最小的发射燃料量。如果一个燃料只能起飞或着陆1吨的火箭，则永远无法使火箭起飞或着陆。
int n;
double p,ans,m,a[10001],b[10001];
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>m;
int f=1;
F(i,0,n-1)
{
CI a[i];
if (a[i]==1) f=0;
}
F(i,0,n-1)
{
CI b[i];
if (b[i]==1) f=0;
}
ans=m;
if (f)
{
FD(i,n-1,0)
{
p=ans*1.0/(b[(i+1)%n]-1);
ans+=p;
p=ans*1.0/(a[i]-1);
ans+=p;
}
CO fixed << setprecision(6)<< ans-m L;
// printf("%lf\n",ans-m);
}
else
{
CO -1 L;
// printf("-1\n");
}
return 0;
}#JC0307. Hamburgers
利用数学关系硬算即可。
LL n[3],p[3],r,ans,t[3],z[3],am,m;
string s;
LL z3()
{
m=min(z[0],min(z[1],z[2]));
ans+=m;
F(i,0,2)
n[i]-=m*t[i];
}
LL z2()
{
m=0x7fffffffffffffff;
int o;
F(i,0,2)
if (z[i]) m=min(m,z[i]);
else o=i;
if ((t[o]-n[o])*p[o]<=r)
{
r-=(t[o]-n[o])*p[o];
ans++;
m--;
F(i,0,2)
n[i]-=t[i];
n[o]=0;
m=min(m,r/(t[o]*p[o]));
ans+=m;
r-=m*t[o]*p[o];
F(i,0,2)
if (z[i]) n[i]-=m*t[i];
}
}
LL z1()
{
m=0;
int o1=0,o2=0,y;
F(i,0,2)
if (z[i])
{
y=i;
m=z[i];
}
else
{
if (!o1) o1=i;
else o2=i;
}
if (((t[o1]-n[o1])*p[o1]+(t[o2]-n[o2])*p[o2])<=r)
{
r-=((t[o1]-n[o1])*p[o1]+(t[o2]-n[o2])*p[o2]);
ans++;
m--;
n[y]-=t[y];
n[o1]=0;
n[o2]=0;
m=min(m,r/(t[o1]*p[o1]+t[o2]*p[o2]));
ans+=m;
r-=m*(t[o1]*p[o1]+t[o2]*p[o2]);
n[y]-=m*t[y];
}
}
LL z0()
{
F(i,0,2)
am+=p[i]*t[i];
if (((t[0]-n[0])*p[0]+(t[1]-n[1])*p[1]+(t[2]-n[2])*p[2])<=r)
{
r-=((t[0]-n[0])*p[0]+(t[1]-n[1])*p[1]+(t[2]-n[2])*p[2]);
ans++;
}
m=r/am;
ans+=m;
r-=m*am;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI s;
CII(n,0,2)
CII(p,0,2)
CI r;
F(i,0,s.size()-1)
{
if (s[i]=='B') t[0]++;
if (s[i]=='S') t[1]++;
if (s[i]=='C') t[2]++;
}
F(i,1,4)
{
int on=0;
F(i,0,2)
{
if (t[i]) z[i]=n[i]/t[i];
else z[i]=0x7fffffffffffffff;
if (z[i]) on++;
}
if (on==3) z3();
if (on==2) z2();
if (on==1) z1();
if (on==0) z0();
}
CO ans L;
return 0;
}#JC0308. Keshi Is Throwing a Party
利用二分，判断是否能找到中间值m个人满足题目要求。
int t;
int n,a[200005],b[200005];
int check(int m)
{
int c=0;
F(i,1,n)
if (m-c-1<=a[i]&&c<=b[i]) c++;
return c>=m;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI n;
F(i,1,n)
CI a[i]>>b[i];
int l=0,r=n+1;
while (l<=r)
{
int m=(l+r)/2;
if (check(m)) l=m+1;
else r=m-1;
}
CO r L;
}
return 0;
}#JC0309. Monthly Expense
利用二分，查找合适的花费值，l的初始值为每天花费的最小值，r的初始值为总花费。判断是否能分出M组。
int n,m,a[100005];
int check(int mid)
{
int x=1,t=0;
F(i,1,n)
{
if (t+a[i]<=mid) t+=a[i];
else
{
t=a[i];
x++;
}
}
return x<=m;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>m;
int l=0,r=0;
F(i,1,n)
{
CI a[i];
l=max(l,a[i]);
r+=a[i];
}
while (l<=r)
{
int mid=(l+r)/2;
if (check(mid)) r=mid-1;
else l=mid+1;
}
CO l L;
return 0;
}#JC0310. New Year's Problem
利用二分，l和r寻找joy值，然后将矩阵中的每一个joy值减去中间值m，并判断每一列是否都有一个值大于m，任意有一行有两个值大于m。
int t,n,m;
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI m>>n;
int a[m+1][n+1];
int l=0x3f3f3f,r=0;
F(i,1,m)
F(j,1,n)
{
CI a[i][j];
l=min(l,a[i][j]);
r=max(r,a[i][j]);
}
while (l<=r)
{
int mid=(l+r)/2;
int b[m+1][n+1],fm[m+1]={0},fn[n+1]={0},f2=1,f3=0;
F(i,1,m)
{
F(j,1,n)
if (a[i][j]>=mid)
{
fm[i]++;
fn[j]++;
}
if (fm[i]>=2) f3=1;
}
F(j,1,n)
if (!fn[j]) f2=0;
if (f2&&f3) l=mid+1;
else r=mid-1;
}
CO r L;
}
return 0;
}#JC0311. Poisoned Dagger
利用二分，查找k值，并判断k值伤害是否能达到h。
LL t,n,h,a[101];
int check(LL m)
{
LL s=m;
F(i,2,n)
s+=min(m,a[i]-a[i-1]);
return s>=h;
}
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI n>>h;
CII(a,1,n);
LL l=1,r=h;
while (l<=r)
{
LL m=(l+r)/2;
if (check(m)) r=m-1;
else l=m+1;
}
CO l L;
}
return 0;
}
Comments | NOTHING