HDOJ 4882 Loves Codefires

ZCC Loves Codefires
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 988 Accepted Submission(s): 500

 

Problem Description

Though ZCC has many Fans, ZCC himself is a crazy Fan of a coder, called “Memset137”.
It was on Codefires(CF), an online competitive programming site, that ZCC knew Memset137, and immediately became his fan.
But why?
Because Memset137 can solve all problem in rounds, without unsuccessful submissions; his estimation of time to solve certain problem is so accurate, that he can surely get an Accepted the second he has predicted. He soon became IGM, the best title of Codefires. Besides, he is famous for his coding speed and the achievement in the field of Data Structures.
After become IGM, Memset137 has a new goal: He wants his score in CF rounds to be as large as possible.
What is score? In Codefires, every problem has 2 attributes, let’s call them Ki and Bi(Ki, Bi>0). if Memset137 solves the problem at Ti-th second, he gained Bi-Ki*Ti score. It’s guaranteed Bi-Ki*Ti is always positive during the round time.
Now that Memset137 can solve every problem, in this problem, Bi is of no concern. Please write a program to calculate the minimal score he will lose.(that is, the sum of Ki*Ti).

Input

The first line contains an integer N(1≤N≤10^5), the number of problem in the round.
The second line contains N integers Ei(1≤Ei≤10^4), the time(second) to solve the i-th problem.
The last line contains N integers Ki(1≤Ki≤10^4), as was described.

 

Output

One integer L, the minimal score he will lose.

 

Sample Input

3
10 10 20
1 2 3

Sample Output

150

Hint
Memset137 takes the first 10 seconds to solve problem B, then solves problem C at the end of the 30th second. Memset137 gets AK at the end of the 40th second.
L = 10 * 2 + (10+20) * 3 + (10+20+10) * 1 = 150.

Author

镇海中学

 

Source

2014 Multi-University Training Contest 2

 

 

贪心题。

很容易想到的是,为了让答案尽可能的小,最好使e小的和K大的尽可能早的完成。也就是说E和K的大小对结果都会有影响。

我们按E/K排个序。

注意冒泡会TLE。。。别问我怎么知道的T T

也别问我为什么不用Sort….因为我不会写CMP函数。。。

噗,其实很简单嘛

poj 1065 Wooden Sticks

Wooden Sticks
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 19008 Accepted: 8012
Description

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l <= l’ and w <= w’. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .
Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1 <= n <= 5000 , that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l1 , w1 , l2 , w2 ,…, ln , wn , each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.
Output

The output should contain the minimum setup time in minutes, one per line.
Sample Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1
Sample Output

2
1
3

 

 

 

贪心题。题目很容易懂,就不翻译了。略水,一遍AC,久违的快感!!!hhhh ,嘛,我为注意节制的(哪和哪!)

把w和l分别按第一关键字和第二关键字排序。

然后扫描一遍,如果符合w[i]>=wk[k]&&l[i]>=lk[k]就更新wk[k]和lk[k],分别表示的是第K的操作下能达到的最大w和l.

如果不符合,则需要增加一分钟的工作时间。同样不要忘记更新。

codeforces 447 B. DZY Loves Strings

简单贪心。

因为填的字母没有次数限制,所以最优策略很容易想到,就是在最后面填最大的。

不用实际去填,算出ans就可以。

hdu 1009 FatMouse’ Trade

 

 

简单贪心….

需要注意的是数据是非负,所以有0的情况要考虑周全,基本都要特殊处理。

多WA了三次,不知道为什么交C++可以过,交G++就不行。

hdu 1050 Moving Tables

 

 

一开始算法想的有点问题。

坑点在于走廊两侧都有房间

也就是说room1和room2对应的位置是一样的

1 to 3 4to6 是没法同时完成的。

做法就是整个扫一遍,看哪个位置的重复次数最大,*10就是答案。