【玲珑杯】A--萌萌哒的第一题

Time Limit：2s Memory Limit：128MByte

Submissions：1234Solved：221

有一批n个数据需要通过rpc调用获取信息，为了加快速度，我们想要把n个数据平均分成若干份，每份的数据量为x（x可以整除n），假设一次rpc调用所需要的时间为a+b*x^2（其中a、b为常数），那么当给出a、b和n的时候，请求出一个x使得总时间最少，若有多个x满足，请输出最小的x。

11

思路：用到高中数学的一个知识点，a+b>=2*sqrt(a/b);当且仅当a==b时，等号成立，即取到最小值。

本题中，要求x的是一个整数，通过推断可得，如果sqrt(a/b)是一个整数，那么可以直接输出；如果不是，那么就要找它两边的整数，才能满足最小的输出。

#include<cstdio>#include<cmath>int main(){	double a,b;                  //sqrt(a/b)就可能不是整数	int n;	while(~scanf("%lf%lf%d",&a,&b,&n))	{		double x;	    x=sqrt(a/b);	    int m=x;//把x的整数部分赋给m，相当于强制转换。	    if(m==x)          //相等则说明x是整数，直接输出	        PRintf("%d/n",m);	    else	    {		    int x1=m;               //x1=x也对		    int x2=m+1;                //写x2=x+1也对，这两个式子找到了x两端的整数		    while(n%x1!=0)					x1--;                   //不能整除，就一直往下找		    while(n%x2!=0)		    	x2++;                             //不能整除，就一直往上找		    if((a+b*x1*x1)/x1*n<=(a+b*x2*x2)/x2*n）         //看哪一个可以使最后结果更小，输出。（抛物线）		        printf("%d/n",x1);		    else 		        printf("%d/n",x2);	    }    }    return 0;}