LightOJ 1275 - Internet Service Providers

ゝ一世哀愁。 2022-08-18 05:57 5阅读 0赞

1275 - Internet Service Providers

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge"><a href="http://lightoj.com/volume_submit.php?problem=1275" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt=""> </a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1275&amp;language=english&amp;type=pdf" rel="nofollow">PDF (English) </a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1275" rel="nofollow">Statistics </a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1275" rel="nofollow">Forum </a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit: <span style="color:rgb(180,95,4)">2 second(s)</span></td> 
   <td>Memory Limit: <span style="color:rgb(180,95,4)">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

A group of **N** Internet Service Provider companies (ISPs) use a private communication channel that has a maximum capacity of **C** traffic units per second. Each company transfers **T** traffic units per second through the channel and gets a profit that is directly proportional to the factor **T(C - T\*N)**. The problem is to compute the smallest value of  **T** that maximizes the total profit the **N** ISPs can get from using the channel. Notice that **N, C, T**, and the optimal **T** are integer numbers.

# Input #

Input starts with an integer **T (≤ 20)**, denoting the number of test cases.

Each case starts with a line containing two integers **N** and  **C (0 ≤ N, C ≤ 109)**.

# Output #

For each case, print the case number and the minimum possible value of  **T** that maximizes the total profit. The result should be an integer.

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sample Input</h1> </td> 
   <td> <h1>Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>6</p> <p>1 0</p> <p>0 1</p> <p>4 3</p> <p>2 8</p> <p>3 27</p> <p>25 1000000000</p> </td> 
   <td> <p>Case 1: 0</p> <p>Case 2: 0</p> <p>Case 3: 0</p> <p>Case 4: 2</p> <p>Case 5: 4</p> <p>Case 6: 20000000</p> </td> 
  </tr> 
 </tbody> 
</table>

解题思路

题目大意给出N,C，满足数学式T\*（C-N\*T），问当T取什么值（整数值）时能让这个函数式的值最大。（T取满足条件的最小值）。

题解：很明显，就是一个求一元二次方程最高点横坐标的问题。顶点坐标(-b/(2\*a)，(4\*a\*c-b\*b)/(4\*a))。要注意的地方是求出T后，是向下取整的，最大的整数最高点可能落在T+1上，这里需要比较一下。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int cn=0;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		long long n,m;
    		scanf("%lld%lld",&n,&m);
    		printf("Case %d: ",++cn);
    		if(n==0||m==0)
    		{
    			printf("0\n");
    		}
    		else
    		{
    			long long cm1,cm,a1,a2;
    			cm=(m/(2*n));
    			a1=(-n*cm*cm)+m*cm;
    			cm1=cm+1;
    			a2=(-n*cm1*cm1)+m*cm1;
    			if(a2>a1)
    			{
    				printf("%lld\n",cm1);
    			}
    			else
    			printf("%lld\n",cm);
    		}
    	}
    	return 0;
    }