#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e2 + 7;
int n, t, a[N], d[N], l[N], spend[N];
int get(int k) { // 在spend[i]的时间下在第个i鱼塘能调到的鱼的数量
return max(0LL, a[k] - d[k] * spend[k]); // 不可能出负数
// 修正:加上LL,确保比较的是long long类型
}
int work(int n, int t) { // 表示t分钟内在前n个鱼塘种钓取得的最大值
int res = 0;
memset(spend, 0, sizeof spend);//spend[i]表示在第i个鱼塘种花费的时间
for (int i = 0; i < t; i++) {//对于每一分钟
int temp = 1; // 先假设在第一个鱼塘钓的最多:这一分钟给了第一个鱼塘
for (int j = 2; j <= n; j++) {
if (get(temp) < get(j)) temp = j;//对于后面的鱼塘 如果能得到的更多
}
res += get(temp); //加上得到鱼的数量
spend[temp]++; // 在这个鱼塘里面钓鱼的时间+1
}
return res;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];//a[i] 表示第一分钟第i个鱼塘可以吊到a[i]条鱼
}
for (int i = 1; i <= n; ++i) {
cin >> d[i];//表示每分钟减少d[i]个
}
for (int i = 2; i <= n; i++) {
cin >> l[i];//从起点到达 i所需要的时间
l[i] += l[i - 1]; // 表示从第一个鱼塘到第i个鱼塘路上花的总时间
}
cin >> t;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (t - l[i] >= 0) { // 修正:判断是否t-l[i]为负数
ans = max(ans, work(i, t - l[i]));
}//如果能跑到 那就跑一下然后取最大只
}
cout << ans << '\n'; // 修正:输出ans
return;
}
signed main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
int n,m,sum=0;//sum用于记录全部的和
int a[N],b[N];
bool check(int mid){//可以升级的能量值的上限
int res=0;
for(int i=1;i<=n;i++){//对于每一个技能
if(a[i]>=mid){//如果可以大于边界值
res+=(a[i]-mid)/b[i]+1;//表示需要选择的次数
}
}
return res>=m;//与其他值扯上关系
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
int l=0,r=1e6;//表示每个技能可以升的能量边界值
while(l<r){// 二分只是为了得到这个可以做的边界值
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
} //二分出来的r的意思是能量值>=r的都可以加上//可能冲覅
int ans=0,cnt=0;
for(int i=1;i<=n;i++){//如果起始的值>=r
if(a[i]>=r){
int c=(a[i]-r)/b[i]+1;//数量
int end=a[i]-(c-1)*b[i];
cnt+=c;//cnt可能一次加的超过m
ans+=(long long)(a[i]+end)*c/2; //(首项+尾项)*项数/2
}
}//不管 反正减去小的,临界值的个数一定大于等于cnt-m个
cout<<ans-(cnt-m)*r; //可能cnt出来并不是直接等于m而是大于m
return ;
}
signed main(){
int t=1;
while(t--)solve();
return 0;
}
看数据范围2e6可以二分 二分出可以加的能量值的临界值 然后遍历每个技能 加上选择的次数cnt 和增加的技能量ans cnt大于等于m 当cnt大于m时 cnt-m需要删除
下说明ans中后cnt-m个一定是边界值 假设取到l的次数为p次如果cnt+p<m 那么说明l-1也应该被取到 所以cnt+p>=m