好久不更新主要是怠惰了。。。。还要加强训练。

题意分析与思路

注意到这样一句话：

our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

这种最大化最小、最小化最大，显然是二分。

如何二分呢，枚举分成k份中各份的最大值，判断在$max_t$的情况下能否分成$\le k$份，能的话那么我们的$max_t$还能更小，不然就得变大。虽然思路很简单，但是由于不熟练，还是写的满磕磕绊绊的，对状态细节的把握不熟练。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ALL(x) (x).begin(),(x).end()

#define ZERO(x) memset((x),0,sizeof(x))

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

int p[505],m,k;

bool judge(int threshold)

{

    int tmp=p[m],cnt=1;

    for(int i=m-1;i>=1;--i)

    {

        if(tmp+p[i]<=threshold)

        {

            tmp+=p[i];

        }

        else

        {

            cnt++;

            tmp=p[i];

        }

    }

    if(cnt<=k) return true;

    else return false;

}

int main()

{

    int kase; cin>>kase;

    while(kase--)

    {

        cin>>m>>k;

        ll l=-1,r=0;

        for(int i=1;i<=m;++i)

        {

            cin>>p[i];

            r+=p[i];

            l=max(l,(ll)p[i]);

        }

        while(l<r)

        {

            int mid=(l+r)/2;

            if(judge(mid)) r=mid;

            else l=mid+1;

        }

        int tmp=0,cnt=1;

        bool cur[505]; memset(cur,false,sizeof(cur));

        //cout<<l<<" "<<r<<endl;

        for(int i=m;i>=1;--i)

        {

            if(i<=k-cnt) { cur[i]=true; cnt++; /*cout<<i<<" set"<<endl;*/ }

            else

            {

                if(tmp+p[i]<=l)

                tmp+=p[i];

                else

                {

                    //cout<<i<<" put"<<endl;

                    tmp=p[i];

                    cur[i]=true;

                    cnt++;

                }

            }

        }

        for(int i=1;i<=m;++i)

        {

            cout<<p[i];

            if(i==m) cout<<endl;

            else if(cur[i]) cout<<" / ";

            else cout<<" ";

        }

    }

    return 0;

}

巴特西

「个人训练」Copying Books（UVa714）

题意分析与思路

代码

最新文章

热门文章