放牧代码和思想
专注自然语言处理、机器学习算法

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 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    请问,判断二分结束的条件是如何确定的呢?什么时候是lb1?

    李宏扬1年前 (2016-02-24)回复
    • 其实都可以,如果是用ub-lb>1来判断,循环里面就可以写成ub=mid,lb=mid,
      如果是ub>lb的话,循环里面可以写成ub=mid,lb=mid+1,另外,附个人博客地址http://www.cnblogs.com/akrusher/

      杨万里1年前 (2016-04-01)回复
      • 666[嘻嘻]

        李宏扬1年前 (2016-04-06)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机