钓鱼1
2024年12月24日大约 2 分钟
70 分
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100;
int n, T;
int x[MAXN + 5], a[MAXN + 5], b[MAXN + 5];
priority_queue<pair<int, int>> q;
int cal(int pos, int tt)
{
while (!q.empty())
q.pop();
for (int i = 1; i <= pos; i++)
q.push(make_pair(a[i], b[i]));
int now = 0;
while (tt >= 5)
{
auto ab = q.top();
q.pop();
q.push(make_pair(ab.first - ab.second, ab.second));
now += max(ab.first, 0LL);
tt -= 5;
}
return now;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> T;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
// 枚举走到了第几个钓鱼点
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (x[i] * 2 > T)
continue;
ans = max(ans, cal(i, T - x[i] * 2));
}
cout << ans;
return 0;
}
100 分
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100;
int n, T;
int x[MAXN + 5], a[MAXN + 5], b[MAXN + 5];
priority_queue<pair<int, int>> q;
// siz 及以上数量的次数都钓完,时间够不够
bool calTime(int pos, int siz, int tt)
{
int cnt = 0;
for (int i = 1; i <= pos; i++)
{
if (a[i] < siz)
continue;
cnt += (a[i] - siz) / b[i] + 1;
}
return cnt * 5 <= tt;
}
// 1~pos 在 tt 的时间最多钓多少条
int cal(int pos, int tt)
{
int minSiz = 0; // minSiz 大小的鱼可以无限钓
for (int i = 1; i <= pos; i++)
if (b[i] == 0)
minSiz = max(minSiz, a[i]);
int siz = -1; // 时间够把所有 now 条以上的次数都抓完
int l = minSiz + 1;
int r = 1'000'000'000;
while (l <= r)
{
int mid = (l + r) / 2;
if (calTime(pos, mid, tt))
{
siz = mid;
// mid 数量的都能搞完,就看看更小的全搞完时间行不行
r = mid - 1;
}
else
{
// mid 数量的搞不完,那就看看多大的能搞完
l = mid + 1;
}
}
int now = 0; // 总鱼数
int ttt = 0; // 总时间
for (int i = 1; i <= pos; i++)
{
if (a[i] >= siz)
{
int num = (a[i] - siz) / b[i] + 1; // 项数
int s = a[i]; // 第一次
int e = a[i] - b[i] * (num - 1); // 最后一次
now += (s + e) * num / 2;
ttt += num * 5;
}
}
// 多余时间不停钓 minSiz 大小的鱼
return now + (tt - ttt) / 5 * minSiz;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> T;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
// 枚举走到了第几个钓鱼点
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (x[i] * 2 > T)
continue;
ans = max(ans, cal(i, T - x[i] * 2));
}
cout << ans;
return 0;
}