UVA-714-二分+贪心

  题意: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;
}

  

上一篇:kubernetes版本apiversion简单说明


下一篇:String类的一些常见的获取方法(5)