欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

例题8-10:抄书(二分答案+贪心)

程序员文章站 2022-06-03 13:57:52
...

例题8-10:抄书
例题8-10:抄书(二分答案+贪心)
由于要求有多解时s(1)尽量小,s(1)一样时s(2)尽量小,采用贪心从后往前找

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<list>
#include<deque>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const double eps = 1e-6;
const int INF = 1 << 30;
const int dir[4][2] = {1,0,0,1,0,-1,-1,0};
int T, n, k;
ll a[550], sum, mm;
bool judge(ll x)
{
    ll tot = 0, ans = 1;
    for(int i = 0; i < n; i++)
    {
        if(tot + a[i] <= x)tot+=a[i];
        else tot = a[i],ans++;
        if(ans > k)return false;
    }
    return true;
}
void input()
{
    sum = 0, mm = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        mm = max(mm, a[i]);
        sum += a[i];
    }
}
void out(ll x)
{
    //cout<<x<<endl;
    ll tot = 0, ans = 1;
    bool v[550];
    memset(v, 0, sizeof(v));
    for(int i = n - 1; i >= 0; i--)///贪心
    {
        if(tot + a[i] <= x)tot+=a[i];
        else{
            tot = a[i];
            v[i] = 1;
            ans++;
        }
    }
    for(int i = 0; i < n && ans < k; i++)
    {
        if(!v[i])v[i] = 1, ans++;
    }
    for(int i = 0; i < n - 1; i++)
    {
        cout << a[i] << " " ;
        if(v[i])cout<<"/ ";
    }
    cout<<a[n - 1]<<endl;
}
void solve(ll x, ll y)
{
    ll m;
    while(x < y)
    {
        m = (y + x) / 2;
        if(judge(m))y = m;
        else x = m + 1;
    }
    sum = 0;
    ///这里的答案是x!!!
    out(x);///输出很复杂;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        input();
        solve(mm, sum);
    }
    return 0;
}