类似技能升级
比这题多一个枚举然后得出最大值
#include <bits/stdc++.h>
#define PI acos(-1)
#define all(a) (a).begin(), (a).end()
#define erjinzhi(n) __builtin_popcountll(n);
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
const char nl = '\n';
const int N = 2e5 + 10;
int a[N], b[N], t[N];
int n, T;
bool check(int x, int k)
{
LL sum = 0;
for (int i = 1; i <= k; ++i)
if (a[i] >= x)
{
int num = (a[i] - x) / b[i] + 1;
sum += num;
}
return sum >= T;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> b[i];
for (int i = 1; i < n; ++i)
cin >> t[i];
cin >> T;
LL ans = 0;
for (int i = 1; i < n; ++i)//枚举走到每一个鱼塘的情况
{
T -= t[i];
if (T <= 0)
break;
int l = 0, r = 1e6;
while (l < r) //二分找到x
{
int mid = (l + r + 1) >> 1;
if (check(mid, i + 1))
l = mid;
else
r = mid - 1;
}
LL sum = 0;
LL cnt = 0;
for (int j = 1; j <= i + 1; ++j) //累加每个数列中大于x的值
{
if (a[j] >= l)
{
LL num = (a[j] - l) / b[j] + 1;
LL x = num * a[j] - (num * (num - 1) / 2) * b[j];
sum += x;
cnt += num;
}
}
ans = max(ans, sum - (cnt - T) * l);//答案取最大值
}
cout << ans;
return 0;
}
大佬我想问一下,为什么二分的时候r=1e6,题目好像没有给出最初能钓鱼的范围,只给出了答案是在int的范围之内,但是有可能能钓鱼的个数初值>1e6
因为二分求的是在尽可能用完所有时间的情况下,最后选择的那个鱼塘能钓到的鱼的数量,其实r写1e3就行了,因为N最大为1000
为什么,n不是鱼塘的个数么,但是二分的不是鱼的数量么
说错了,不是N,是“第1分钟能钓到的鱼的数量(1..1000)”
哦哦,原来表格上写了第一分钟钓到鱼的数量呀,我眼瞎了,呜呜呜
谢谢大佬