UVA-714-二分+贪心

时间：2023-12-14 18:05:08

　　题意：K个人复制M本书,每本书有Pi页,要求每个人都能分到至少一本书,如果分到多本书籍,分到的书籍编号是连续的,并且K个人里面分到的书籍总页数最大的那个人总数最小.

如果有多组解,保证 K1 < K2 < K3.....

解法:

二分最小的最大值,答案范围肯定是(L=0)  -  (R=total_page), 假设答案是ans= (L+R)/2,假设当前ans是正确的,那么给K个人分配,如果成功那么最优解的范围是 ans - R，

如果不成功,那么最优解是0 - ans,

#include "pch.h"

#include <string>

#include<iostream>

#include<map>

#include<memory.h>

#include<vector>

#include<algorithm>

#include<queue>

#include<vector>

#include<stack>

#include<math.h>

#include<iomanip>

namespace cc

{

	using std::cout;

	using std::endl;

	using std::cin;

	using std::map;

	using std::vector;

	using std::string;

	using std::sort;

	using std::priority_queue;

	using std::greater;

	using std::vector;

	using std::swap;

	using std::stack;

	class Point

	{

	public: int l, r, len;

			Point() {};

			Point(int x, int y) :l(x), r(y) {

				if (l < 0)

					this->len = r;

				else

					this->len = r - l; 

			};

			int operator < (Point& p)

			{

				int l1 = p.l;

				int l2 = this->l;

				if (l1 < 0)

					l1 = 0;

				if (l2 < 0)

					l2 = 0;

				if (l1 < l2)

					return 0;

				if (l1 == l2)

					return p.len < this->len;

				return 1;

			}

	};

	constexpr int N = 502;

	int M, K;

	int cases;

	int assignTotal = 0;

	//由后往前

	int assignIndex[N];

	long long pages[N];

	long long totalPages = 0;

	int avg = 0;

	/*

	*

	*ok return 1

	*/

	int cal(long long cur)

	{

		int ass[N];

		int assIndex = 0;

		long long curTotal = 0;

		int i = -1;

		for (i=M-1;i>=0;i--)

		{

			if (pages[i] > cur)

				return 0;

			if (curTotal+pages[i] > cur || (i + 1 < K - assIndex))

			{

				ass[assIndex++] = i+1;

				if (assIndex > K)

					return 0 ;

				curTotal = 0;

				curTotal += pages[i];

				continue;

			}

			curTotal += pages[i];

		}

		if (assIndex != K-1)

			return 0;

		ass[assIndex++] = 0;

		//assIndex = K

		//copy

		memcpy(assignIndex,ass,sizeof(int)*assIndex);

		assignTotal = assIndex;

		return 1;

	}

	void solve()

	{

		cin >> cases;

		while (cases--)

		{

			totalPages = 0;

			avg = 0;

			assignTotal = 0;

			cin >> M >> K;

			for(int i=0;i<M;i++)

			{

				cin >> pages[i];

				totalPages += pages[i];

			}

			long long l = 0, r = totalPages;

			while (l < r-1)

			{

				long long mid = (l + r) / 2;

				int ok = cal(mid);

				if (ok)

				{

					//mid是最优

					r = mid;

				}

				else

				{

					//mid不是最优

					l = mid;

				}

			}

			//print

			int cpi = assignTotal-2;

			for (int  i=0;i < M;i++)

			{

				if (cpi >= 0 && i == assignIndex[cpi])

				{

					cout << " /";

					--cpi;

				}

				if (i == 0)

					cout << pages[i];

				else

					cout << " " << pages[i];

			}

			cout << endl;

		}

	}

};

int main()

{

#ifndef ONLINE_JUDGE

	freopen("d://1.text", "r", stdin);

#endif // !ONLINE_JUDGE

	cc::solve();

	return 0;

}

　　

相关文章