UVA - 714 Copying Books （抄书）（二分+贪心）

题意：把一个包含m个正整数的序列划分成k个（1<=k<=m<=500）非空的连续子序列，使得每个正整数恰好属于一个序列（所有的序列不重叠，且每个正整数都要有所属序列）。设第i个序列的各数之和为S(i)，你的任务是让所有的S(i)的最大值尽量小。如果有多解，S(1)应尽量小，如果仍有多解，S(2)应尽量小，依此类推。

分析：

1、二分最小值x。

2、判断当前x是否满足条件时，从右往左尽量划分，若cnt<k，则从0开始依次标为分界点，这样可满足S(1)，S(2)，……，尽量小。

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int MAXN = 500 + 10;

const int MAXT = 10000 + 10;

using namespace std;

LL a[MAXN];

int m, k;

int cnt;

int vis[MAXN];//分界点

bool judge(LL x){

    memset(vis, 0, sizeof vis);

    cnt = 0;

    int pos = m - 1;

    while(pos >= 0){

        int num = 0;//当前序列中的元素

        LL sum = 0;

        while(pos >= 0 && sum + a[pos] <= x){

            sum += a[pos];

            ++num;

            --pos;

        }

        if(!num) return false;//若当前序列中没有元素，说明x太小

        if(pos >= 0) vis[pos] = 1;

        ++cnt;

    }

    if(cnt > k) return false;

    return true;

}

void solve(){

    LL l = 0, r = 1e15;

    while(l < r){

        LL mid = l + (r - l) / 2;

        if(judge(mid)) r = mid;

        else l = mid + 1;

    }

    if(judge(r)){

        for(int i = 0; i < m - 1 && cnt < k; ++i){

            if(!vis[i]){

                vis[i] = 1;

                ++cnt;

            }

        }

        for(int i = 0; i < m; ++i){

            if(i) printf(" ");

            printf("%lld", a[i]);

            if(vis[i]) printf(" /");

        }

        printf("\n");

    }

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        scanf("%d%d", &m, &k);

        for(int i = 0; i < m; ++i){

            scanf("%lld", &a[i]);

        }

        solve();

    }

    return 0;

}

巴特西

UVA - 714 Copying Books （抄书）（二分+贪心）

最新文章

热门文章