Posted on 2010-08-07 13:41
MiYu 閱讀(579)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 水題 ) 、
ACM ( 數論 )
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2078
題目描述:
Problem Description
為了能過個好年，xhd開始復習了，于是每天晚上背著書往教室跑。xhd復習有個習慣，在復習完一門課后，他總是挑一門更簡單的課進行復習，而他復習這門課的效率為兩門課的難度差的平方,而復習第一門課的效率為100和這門課的難度差的平方。xhd這學期選了n門課，但是一晚上他最多只能復習m門課，請問他一晚上復習的最高效率值是多少？
Input
輸入數據的第一行是一個數據T，表示有T組數據。
每組數據的第一行是兩個整數n(1 <= n <= 40)，m(1 <= m <= n)。
接著有n行，每行有一個正整數a(1 <= a <= 100)，表示這門課的難度值。
Output
對于每組輸入數據，輸出一個整數，表示最高效率值。
Sample Input
2
2 2
52
25
12 5
89
64
6
43
56
72
92
23
20
22
37
31
Sample Output
5625
8836
由題意我們很容易了解到 : 前一門課為 N, 后一門課為 M , 則學習 M 課的效率為 ( N - M )2 , 那么學習第一節的效率為
( 100 - N )2 , 有題目我們知道: 下一門需要學習的課比上一次更 簡單, 所以 N > M, 那么此時學習的效率為 :
F1 = ( 100 - N )2 + ( N - M )2 = 1002 - 2*100*N + N2 + N2 - 2*N*M + M2 = 1002 + M2 - 2*N*( 100+M-N );
而直接學習最簡單的課程的效率為:
F2 = ( 100 - M )2 = 1002 +M2 - 2*100*M
因為 2*N*( 100+M-N ) - 2*100*M = ( N - M ) * ( 200 - 2*N ) ,有上面的分析我們知道 N > M , N < 100 , 于是就有
( N - M ) * ( 200 - 2*N ) > 0 ; 也就是說 F2 > F1 ;
有分析可以看出 , 要想效率最高, 只需要找出簡單的課程直接學習就可以了.
代碼如下 :
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
#include <iostream>
using namespace std;
int main ()
{
int T;
cin >> T;
while ( T -- )
{
int n,m;
cin >> n >> m;
int min = 100;
for ( int i = 1; i <= n; ++ i )
{
cin >> m;
if ( min > m )
{
min = m;
}
}
cout << ( 100 - min ) * ( 100 - min ) << endl;
}
return 0;
}