• 2021RoboCom机器人开发者大赛（初赛）
• 2021RoboCom机器人开发者大赛（复赛）
  • 拼题A打卡奖励

2021RoboCom机器人开发者大赛（初赛）

pta 题解

2021RoboCom机器人开发者大赛（复赛）

pta 题解

拼题A打卡奖励

题面：


题意：
普通背包问题。你有 m 的时间可以做 n 张打卡卷，做完第 i 张打卡卷需要 \(m_i\) 的时间，做完可以获得 \(c_i\) 的金币。问你你在 m 时间里能获得的最大金币数
思路：
利用普通背包问题的求解过程超时，，，因为m太大了！

怪，不知道普通背包问题怎么优化了。。。
训练的时候用了一种奇怪的做法过了，这里摘记一下
就是对于每一张试卷存一个金币数与花费时间的比值，再按照这个比值从大到小排序，利用尺取法求解答案。
还是感觉这个做法很怪？

#include<bits/stdc++.h>
#define ll long long 

using namespace std;
const int maxm=2e5+5;
ll n,m;
struct node{
	ll min,c;
	double t;
}p[maxm];

void solve(){
	cin>>n>>m;
	for(int i=0;i<n;++i){
		cin>>p[i].min;
	}
	for(int i=0;i<n;++i){
		cin>>p[i].c;
		p[i].t=1.0*p[i].c/p[i].min;
	}
	sort(p,p+n,[](node x,node y){
		return x.t>y.t;
	});
	int cnt=0,sum=0,ans=0,l=0,r=0;
	while(l<n&&r<n){
		if(cnt+p[r].min<=m){
			cnt+=p[r].min;
			sum+=p[r].c;
			if(sum>ans){
				ans=sum;
			}
			++r;
		}else{
			cnt-=p[l].min;
			sum-=p[l].c;
			++l;
		}
	}
	cout<<ans<<'\n';
	return ;
}

signed main(){
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
	return 0;
}