学步园

论单机幻影刺客的最佳打野路线

Description

DOTA是一款很棒的游戏，今天，天梯积分快2000的GOD姚又开始玩起了DOTA。
这次，GOD姚选了“幻影刺客”这么个打野很厉害的英雄。GOD姚决定专心在野区打钱，为n分钟后决定胜负的团战做准备。现在GOD姚可以在基地花费1金币将自己的打野效率（每分钟在野区赚到的钱）提升1,不过基地到野区有一段距离，而要想来回基地和野区一次必须要花费一个传送卷轴，现在GOD姚身上只有2个传送卷轴，为了使自己最后赚得的总金钱最多，GOD姚通过一番计算后知道了在何时使用传送卷轴可以使自己n分钟后拥有的金钱最多。
0分钟时刻GOD姚拥有的金钱数量为0，GOD姚初始打野效率是1，你能求出GOD姚应该在何时使用传送卷轴才能使自己n分钟后拥有的金钱最多吗？

注：打野：通过杀死野外怪物赚取金钱；
野区：有野外怪物的区域；
基地：可以提升自己打野效率的地方；
传送卷轴：可以快速往返基地和野区，由于花费时间极短，可忽略不计；
团战：敌我双方全员参与的战斗；

Input

第一行一个数T(0 < T<=200)，表示有T组CASE，对于每组CASE，仅包含一个整数n，（4<=n<=100000)。

Output

对于每组CASE，输出一行，包含两个数t1,t2用空格隔开，分别表示GOD姚为了能在n分钟后身上的金钱最多，分别在t1分钟末和t2分钟末使用了传送卷轴，如果有多组不同的解输出字典序最小的一组，即输出t1最小的那组解，如果仍有多组解，输出t2最小的那组解。

Sample Input

1
4

Sample Output

1 2

Hint

GOD姚在第1分钟末传送回基地，花费1单位金钱使自己打野效率提升1，在第2分钟末再次传送回家，花费2单位金钱使自己的打野效率提升2，此时自己打野效率为4，在接下来的两分钟里共可获得8单位的金钱，GOD姚n分钟后能拥有的最大金钱数是8.

Source

t1从1开始到n-2循环，把t1当成定值，求出t2在何时有最大值（通过推导出的公式），把s最大的情况输出

#include<iostream>

using namespace std;

int main(void)
{
	int T;
	long long max;
	long long t1,t2,s;
	cin>>T;
	while(T--)
	{
		long long n,tmp;
		cin>>n;
		max=0;
		for(long long i=1;i<n;i++)
		{
			tmp=(n+i-1)/2;
			if(tmp<=i)
				tmp=i+1;
			s=(i+1)*(tmp-i+1)*(n-tmp);
			if(s>max)
			{
				t1=i;
				t2=tmp;
				max=s;
			}
		}
		cout<<t1<<' '<<t2<<endl;
	}
	return 0;
}