正題

題目鏈接: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【贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。