jtahstu的博客

Git仓库   英文博客  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> hdu-2078-复习时间(数学)

hdu-2078-复习时间(数学)

hdu-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

简单的数学,题目的代码很简单
例如:我们拿两个数和三个数做下比较
100 x
(100-x)^2=10000-200x+x^2 (1)
100 y x
(100-y)^2+(y-x)^2=(10000-200y+y^2)-(y^2-2xy+x^2) (2)
两式相减
(10000-200x+x^2)-((10000-200y+y^2)-(y^2-2xy+x^2))
=-200x+200y-2y^2+2xy
=200(y-x)+2y(x-y)
=(200-2y)*(y-x)
因为1 < y <= 100,所以结果大于等于0
显然只要y不是100,实际y应该是个1~100的数,那么多一个数反而会使结果变小
而题目要求最大效率,那我们只要拿最小的一个数就行了
所以代码很简单,即(100-min)^2就是结果了


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HDU2078 {
    class Program {
        static void Main(string[] args) {
            int t = int.Parse(Console.ReadLine());
            while (t-- > 0) {
                string[] s = Console.ReadLine().Split();
                int n = int.Parse(s[0]),a=int.Parse(Console.ReadLine());
                for (int i = 1; i < n; i++) {
                    int temp =int.Parse(Console.ReadLine());
                    if (temp < a) a = temp;
                }
                Console.WriteLine((100 - a) * (100 - a));
            }
        }
    }
}
 

by jtahstu on 2015/8/13 0:40:17


---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

35 + 36 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……