紫书习题 10-20 UVa 1648 (推公式）

设一次上去a层，一次下去b层，有x次上去，有(n-x)次下去

则ax - (n-x)b >= 1

x >= (nb+1) / (a+b)

如果可以整除， x = (nb+1) / (a+b)

否则 x = (nb+1) / (a+b) +１

算出ｘ后再带到ax - (n-x)b里就是当前的最优答案

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

int main()

{

	int n, m;

	while(~scanf("%d%d", &n, &m))

	{

		int a, b, ans = 2e9;

		while(m--)

		{

			scanf("%d%d", &a, &b);

			int x;

			if((n * b + 1) % (a + b) == 0) x = (n * b + 1) / (a + b);

			else x = (n * b + 1) / (a + b) + 1;

			ans = min(ans, a * x - (n - x) * b);

		}

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

紫书习题 10-20 UVa 1648 (推公式）

最新文章

热门文章

巴特西

紫书 习题 10-20 UVa 1648 (推公式）

最新文章

热门文章

紫书习题 10-20 UVa 1648 (推公式）