目录
拼题A打卡奖励
题面：
题意：
普通背包问题。你有 m 的时间可以做 n 张打卡卷，做完第 i 张打卡卷需要 \(m_i\) 的时间，做完可以获得 \(c_i\) 的金币。问你你在 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;
}