U33405 纽约（二分）

【题目描述】

　　　　牧民 Azone 需要多次往返于两个草场之间运输家当。为了顺利转场，Azone 决定花费 w元津巴布韦币，购买一辆载重为 w 的汽车。共有 n 件家具需要搬运，每件家具的重量为 wi 。Azone 每次出发前，会搬若干件总重不超过 w 的物品上车：出发前，车是空载的，Azone 会选择能搬上车的家具中最重的一件放上车（即该家具之前还未运走且放置该家具后汽车不会超载），然后在剩下的家具中继续选择一件能被搬走的最重的上车，持续装车，直至剩下的家具都塞不上车。装载完毕后，Azone 会开车运走这些家具，卸在目的地，再驾空车返回继续运送，直至转场完毕。Azone 希望在运送次数不超过 R 的情况下完成转场，求 Azone 最少需要购置价值多少的车。

【题目链接】

　　　　https://www.luogu.org/problemnew/show/U33405

【算法】

　　　　直接二分结果不一定是最优解，存在w时可行而w+1不可行的情况。但是若w可行则w+Biase（偏置值>=max（w【i】））必定可行，所以先二分然后往前枚举max（w【i】）个。重点是为什么二分结果不一定是最优解，因为题目当中采取的装载策略（贪心策略：取尽可能重）并非最优策略（贪心成立的时候记得是坐船问题：一个船最多坐两个人，并且有载重限制，可以证明）。

【代码——模拟贪心策略，对每一个家具遍历已经开出的装载集合，若能装则装否则重新开一个集合】

 #include <bits/stdc++.h>

 using namespace std;

 int n,r,i,l,j,R,ans;

 int a[],rec[];

 bool cmp(int a,int b) { return a>b; }

 bool valid(int cur)

 {

     if(cur<a[]) return false;

     memset(rec,,sizeof(rec));

     int tot=;

     for(i=;i<=n;i++) {

         int flag=;

         for(j=;j<=tot;j++)

             if(rec[j]+a[i]<=cur) {

                 rec[j]+=a[i],flag=;

                 break;

             }

         if(!flag) rec[++tot]=a[i];

         if(tot>R) return false;

     }

     return true;

 }

 int main()

 {

     scanf("%d%d",&n,&R);

     for(i=;i<=n;i++) scanf("%d",&a[i]),r+=a[i];

     sort(a+,a+n+,cmp);

     l=a[];

     while(l<r) {

         int mid=(l+r)>>;

         if(valid(mid)) r=mid;

         else l=mid+;

     }

     ans=l;

     for(int i=;i<=a[]&&l-i>=a[];i++)

         if(valid(l-i)) ans=l-i;

     printf("%d\n",ans);

     return ;

 }

巴特西

U33405 纽约（二分）

最新文章

热门文章

巴特西

U33405 纽约 （二分）

最新文章

热门文章

U33405 纽约（二分）