tanxin.cpp

在对问题求解时

#include<iostream>
#include<algorithm>
using namespace std;

int n,k;
int page[501];
bool mk[501];
int ap;

bool ok(__int64 mmax)
{
        int i;
        ap = 0;
        __int64 sum = 0;
        bool flag = 0;

        memset(mk,0,sizeof(mk));

        for(i = n - 1; i >= 0; i--)
        {
                if(sum + page[i] <= mmax)sum += page[i];
                else 
                {
                        sum = page[i];
                        mk[i] = 1;
                        ap++;
                        if(ap >= k)return 0;
                }
        }
        return 1;
} 


__int64 solve(__int64 low,__int64 high)
{
        __int64 mid;
        while(low <= high)
        {
                mid = (low + high) / 2;
                if(ok(mid))high = mid - 1;
                else low = mid + 1;
        }
        return low;
}

int main()
{
//        freopen("data.txt","r",stdin);
        int T;
        int i;
        __int64 mmax,mmin;
        scanf("%d",&T);

        while(T--)
        {
                scanf("%d%d",&n,&k);

                mmax = 0;
                mmin = -1;
                for(i = 0;i < n; ++i)
                {
                        scanf("%d",&page[i]);
                        mmax += page[i];
                        mmin = mmin > page[i] ? mmin : page[i];
                }

                __int64 mans = solve(mmin,mmax);
                
                bool die = ok(mans);

        //        cout<<ap<<endl;
                ap = k - ap - 1;

                for(i = 0; i < n && ap > 0;i++,ap--)
                {
                        if(mk[i])ap++;
                        mk[i] = 1;
                }

                for(i = 0; i < n - 1; ++i)
                {
                        printf("%d ",page[i]);
                        if(mk[i])printf("/ ");
                }
                printf("%d\n",page[n - 1]);
        }
        return 0;
}