正题

题目链接:https://www.luogu.com.cn/problem/P3462

---

题目大意

$n$个容器容量不同，$m$个物品，对于一两个物品$i,j$，若$w_i\le w_j$那么有$w_i|w_j$。
求能够放下的最多物品。

---

解题思路

显然就是一个进位的东西，我们设$f_i$表示第$i$位能装下多少个（优先装大的先）

对于每个容器计算一个总的出$f_i$（不会影响整体）

然后我们将$f_i$往后面进位，不够就的补足知道满。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; ll n,m,v[N],a[N],k[N],s[N],c[N],r[N],ans,cnt; int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",&v[i]);for(ll i=1;i<=m;i++)scanf("%lld",&a[i]);sort(a+1,a+1+m);k[1]=s[1]=a[1];c[1]=cnt=1;for(ll i=2;i<=m;i++)if(a[i]!=a[i-1]) k[++cnt]=a[i]/a[i-1],s[cnt]=a[i],c[cnt]=1;else c[cnt]++;for(ll i=1;i<=n;i++)for(ll j=cnt;j>=1;j--)if(v[i]>=s[j])r[j]+=v[i]/s[j],v[i]%=s[j];ll l=cnt-1;for(ll i=cnt;i>=1;i--){ll w=r[i]*s[i];while(l>0){int use=max(min((c[l]-r[l])*s[l],w),0ll);w-=use;r[l]+=use/s[l];if(!w) break;l--;}r[i]=w/s[i];ans+=min(r[i],c[i]);}printf("%lld",ans); }

总结

以上是生活随笔为你收集整理的P3462-[POI2007]ODW-Weights【贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。