POJ 3104 Drying 题解 《挑战程序设计竞赛》

这是博客的自动同步，我让它自动同步到所有社交网络。有朋友跟我讲人人都快被我刷屏了，真是对不住。其实人人有屏蔽功能，不过我建议取消好友\关注。另外我根本不用人人这种SNS，请不要给我留言，我的强迫症让我保留了人人账号，打扰了。

POJ 3104 Drying

晾衣服：n件衣服各含a_i水分，自然干一分钟一单位，放烘干机一分钟k单位，一次只能晒一件。求最短时间。

取C(mid) := 能在mid分钟内处理完，然后二分即可。

这里有两个很好玩的陷阱

①每分钟烘干k单位的水，于是我就想当然地除k向上取整了((a_i – mid) / k)。其实应该除以k-1，列个详细的算式：

设需要用x分钟的机器，那么自然风干需要mid – x分钟，x和mid需要满足：

k*x + (mid – x) >= a_i，即 x >= (a_i – mid) / (k – 1)。

②当k=1的时候，很显然会发生除零错误，需要特殊处理。

所以应该这么干：

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_A 100000 + 16
int n, a[MAX_A], k;

bool C(int mid)
{
	unsigned long long minutes(0);
	for (int i = 0; i < n; ++i)
	{
		int more = a[i] - mid;
		if (more > 0)
		{
			minutes += (more + k - 1) / k;	// ceil
			if (minutes > mid)
			{
				return false;
			}
		}
	}
	return true;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	cin >> k;
	--k;		// x >= (a_i - mid) / (k - 1)
	if (k == 0)
	{
		cout << *max_element(a, a + n) << endl;
	}
	else
	{
		int lb = *min_element(a, a + n) / k, ub = *max_element(a, a + n);
		while (ub - lb > 1)
		{
			int mid = (lb + ub) >> 1;
			if (C(mid))
			{
				ub = mid;
			}
			else
			{
				lb = mid;
			}
		}
		cout << ub << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3104 Drying 题解 《挑战程序设计竞赛》