五一期间和然然打的团队赛..那时候用然然的号打一场掉一场...七出四..D1是个数据规模较小的题 写了一个暴力过了 面对数据如此大的D2无可奈何 现在回来看 一下子就知道解法了
二分就可以 二分能做多少个 每次对mid求一下不够的差值 比较差值与m的大小进行l与r的变换
由于自己一向对二分比较迷茫 自己琢磨出来一套神奇的办法面对边界数据
当小于和大于的时候 抛弃mid值
当等于的时候 直接break 然后打一发while试试能否向更好的情况偏移
当然在这个题目中 如果是直接break的时候就不用偏移了
使用了llu 如果lld的话貌似会挂的样子
如果没有直接break出来的情况 最后l r mid 之间的差值一定就是1和0 那么l-5一定是小于三者的..
llu小于0会直接转化为极大的值 所以需要if判断一下
该去学习一下二分的姿势了...
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;
unsigned long long int n,m;
unsigned long long int a[100050];
unsigned long long int b[100050];
int main()
{
cin>>n>>m;
for(int i = 1; i<=n; i++)
{
scanf("%llu",&a[i]);
}
for(int i = 1; i<=n; i++)
{
scanf("%llu",&b[i]);
}
unsigned long long int l = 0;
unsigned long long int r = 3e9;
unsigned long long mid;
while(l<r)
{
mid=(l+r)/2;
unsigned long long cz=0;
for(int i = 1; i<=n; i++)
{
unsigned long long aa= a[i]*mid;
if(b[i]<aa)
{
cz+=(aa-b[i]);
}
}
if(cz>m)
{
r=mid-1;
}
else if(cz<m)
{
l=mid+1;
}
else break;
}
unsigned long long cz=0;
for(int i = 1; i<=n; i++)
{
unsigned long long aa= a[i]*mid;
if(b[i]<aa)
{
cz+=(aa-b[i]);
}
}
if(cz==m)
{
printf("%llu
",mid);
return 0;
}
unsigned long long int z;
if(mid<5)
z=0;
else
z=mid-5;
while(true)
{
z++;
unsigned long long x=0;
for(int i=1; i<=n; i++)
{
unsigned long long aa= a[i]*z;
if(b[i]<aa)
{
x+=(aa-b[i]);
}
}
if(x>m)
break;
}
printf("%llu
",z-1);
}