【LightOJ】[1275]Internet Service Providers

问题描述

问题分析

感觉这一题的难点在于……这是道英文题
-.-
然后就是读不懂题目的意思

其实这道题的解法很简单
就是求能让这个一元二次方程取到极值时的整数T的值
……呃
或者说
求出一个整数T 让取它为值时函数结果最大
(因为N>0)

方程其实应该这么写

$$T*(C - T*N)$$

等价于

$$-N*T^2+C*T$$

换成 x 或许更好理解……

$$y=-N*x^2+C*x$$

所以……
很简单嘛

还有需要注意的就是这里要求的是整数T的值
所以需要判断用公式得到的结果是不是整数
如果不是
还需判断它左右两个整数的函数值大小
(还有N==0时需要输出的是0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<math.h>
int main() {
	int T;
	int i;
	long long N,C,x;
	scanf("%d",&T);
	for(i=1; i<=T; i++) {
		scanf("%lld %lld",&N,&C);
		if(!N)
			x=0;
		else {
			x=(C/N)/2;
			if(C%(2*N))
				if((C*x-N*x*x)<(C*(x+1)-N*(x+1)*(x+1)))
					x++;
		}
		printf("Case %d: %lld\n",i,x);
	}
	return 0;
}

题目地址：【Light】[1275]Internet Service Providers