@[A_Đark_Horcrux](/user/54372) ll？
by vandijk @ 2020-11-26 18:48:20
@[orz_MSQ](/user/340345) 开了ll qaq
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int i,j; long long n,w,ans,a[N],b[N],c[N],v[N],f[N];
bool check(int mid)
{
for(i=1;i<=w;i++)f[i]=-1e9+7;
for(i=1;i<=n;i++) c[i]=b[i],v[i]=(long long)a[i]-b[i]*mid;
for(i=1;i<=n;i++)
for(j=w;j>=c[i];j--)
f[j]=max(f[j],(long long)f[j-c[i]]+v[i]);
return f[w]>=0;
}
int main()
{
scanf("%d %d",&n,&w);
for(i=1;i<=n;i++) scanf("%lld %lld",&b[i],&a[i]),a[i]*=1000;
int l=0,r=1000000;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld",ans);
return 0;
}
```
by A_Đark_Horcrux @ 2020-11-26 18:50:54
这题大于 $w$ 的要视为 $w$，所以如果要按原背包的话 $f[w]$ 应该从 $f[w-b[i]...w]$ 转移而不仅是 $f[w-b[i]]$。
by a___ @ 2020-11-26 18:55:17
@[a___](/user/35137) 谢谢大佬
by A_Đark_Horcrux @ 2020-11-26 18:57:04
tql
by 白依尘_轩子墨 @ 2020-11-27 16:17:44
%%cyx
by 白依尘_轩子墨 @ 2020-11-27 16:17:54