SP43题解

Graph · 2023-10-13 13:04:03 · 题解

双倍经验：P1281。

首先，字典序小 \to 前面的少写 \to 后面的多写。

少些不好处理，多写的话能写就写。

二分时间，check 中倒序，贪心的让后面多写，并统计答案，最后输出即可。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=505;
int m,k,a[N],sum,L[N],R[N];

int ll[N],rr[N];
bool check(int x)
{
    int sum=0,tot=k;
    rr[tot]=ll[tot]=m;
    for(int i=m;i>=1;i--)
    {
        if(sum+a[i]<=x)
        {
            sum+=a[i];
            ll[tot]=i;
        }
        else
        {
            tot--;
            if(tot==0)
                return false;
            rr[tot]=ll[tot]=i;
            sum=a[i];
        }
    }
    for(int i=1;i<=m;i++)
        L[i]=ll[i],R[i]=rr[i];
    return true;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>m>>k;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i];
            sum+=a[i]; 
        }
        int lt=0,rt=sum+1;
        while(lt+1<rt)
        {
            int mid=(lt+rt)>>1;
            if(check(mid)==true)
                rt=mid;
            else
                lt=mid;
        }
        for(int i=1;i<=k;i++)
        {
            for(int j=L[i];j<=R[i];j++)
                cout<<a[j]<<" ";
            if(i!=k)
                cout<<"/ ";
        }
        puts("");
    }
    return 0;
}