Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
6
Indexable
Never
#include<iostream>

using namespace std;

int arr[100005],k,n,ans;

void init(){
	cin>>k>>n;
	ans=0;
	for (int i = 0; i < n; i++)
	{
		cin>>arr[i];
	}
}

void solve(){
	int sum = 0;
	int mmax = 0;
	for (int i = 0; i < n; i++)
	{
		if(arr[i] > mmax){
			mmax=arr[i];
		}
		sum+=arr[i];
	}

	
	for (int i = mmax; i <= sum; i++)
	{
		int demKhoi=1;
		int sum1=0;
		for (int j = 0; j < n; j++)
		{
			if(sum1+arr[j] > i){
				demKhoi++;
				sum1=arr[j];
			}
			else
			{
				sum1+=arr[j];
			}
		}

		if(demKhoi<=k){
			ans=i;
			break;
		}
	}
	cout<<ans<<endl;
}

int main(){
	//freopen("input.txt","r",stdin);
	int t;cin>>t;
	for (int i = 1; i <= t; i++)
	{
		init();
		cout<<"#"<<i<<" ";
		solve();
	}
	return 0;
}



#include <stdio.h>

int s[100001];
int N, K;

int check(int big)
{
	int sum = 0;
	int cnt = 1;
    int i;
	for (i = 0; i < N; i++) {
		sum += s[i];
		if (sum > big) {
			cnt++;
			i--;
			sum = 0;
		}
		if (cnt > K)
			return 0;
	}
	return 1;
}

int main()
{
	int test_case;
	int T;
	int left, right, mid;

	//freopen("sample_input.txt", "r", stdin);
	scanf("%d", &T);

	for (test_case = 1; test_case <= T; ++test_case)
	{
		scanf("%d%d", &K, &N);
		left = right = 0;

        int i;
		for (i = 0; i < N; i++) {
			scanf("%d", &s[i]);
			if (s[i] > left)
				left = s[i];
			right += s[i];
		}

		while (left <= right) {
			mid = (left + right) >> 1;
			if (check(mid)) 
				right = mid - 1;
			else
				left = mid + 1;
		}
		printf("#%d %d\n", test_case, left);
	}
	return 0;
}