Posted on 2010-08-07 13:41
MiYu 閱讀(584)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 水題 ) 、
ACM ( 數(shù)論 )
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2078
題目描述:
Problem Description
為了能過個好年，xhd開始復(fù)習(xí)了，于是每天晚上背著書往教室跑。xhd復(fù)習(xí)有個習(xí)慣，在復(fù)習(xí)完一門課后，他總是挑一門更簡單的課進(jìn)行復(fù)習(xí)，而他復(fù)習(xí)這門課的效率為兩門課的難度差的平方,而復(fù)習(xí)第一門課的效率為100和這門課的難度差的平方。xhd這學(xué)期選了n門課，但是一晚上他最多只能復(fù)習(xí)m門課，請問他一晚上復(fù)習(xí)的最高效率值是多少？
Input
輸入數(shù)據(jù)的第一行是一個數(shù)據(jù)T，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)的第一行是兩個整數(shù)n(1 <= n <= 40)，m(1 <= m <= n)。
接著有n行，每行有一個正整數(shù)a(1 <= a <= 100)，表示這門課的難度值。
Output
對于每組輸入數(shù)據(jù)，輸出一個整數(shù)，表示最高效率值。
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 , 則學(xué)習(xí) M 課的效率為 ( N - M )2 , 那么學(xué)習(xí)第一節(jié)的效率為
( 100 - N )2 , 有題目我們知道: 下一門需要學(xué)習(xí)的課比上一次更 簡單, 所以 N > M, 那么此時學(xué)習(xí)的效率為 :
F1 = ( 100 - N )2 + ( N - M )2 = 1002 - 2*100*N + N2 + N2 - 2*N*M + M2 = 1002 + M2 - 2*N*( 100+M-N );
而直接學(xué)習(xí)最簡單的課程的效率為:
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 ;
有分析可以看出 , 要想效率最高, 只需要找出簡單的課程直接學(xué)習(xí)就可以了.
代碼如下 :
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
#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;
}