简单贪心 直接从 J [ i ] F [ i ] \frac{J[i]}{F[i]} F[i]J[i]最大的开始取即可。
/**
*HDU - 1009
*@author Hongchuan CAO
*/
import java.util.Arrays;
import java.util.Scanner;
import java.util.logging.Logger;
public class Main{
private int M,N;
static Logger logger = Logger.getLogger("Main");
public void solve(){
Scanner in = new Scanner(System.in);
while(true) {
M = in.nextInt();
N = in.nextInt();
if(M==-1&&N==-1) break;
Node[] node = new Node[N];
for (int i = 0; i < N; i++) {
node[i] = new Node();
node[i].J = in.nextInt();
node[i].F = in.nextInt();
node[i].res = 1.0 * node[i].J / node[i].F;
}
Arrays.sort(node);
int sum = 0;
double result = 0;
for (int i = 0; i < N; i++) {
if (sum + node[i].F < M) {
result += node[i].J;
sum += node[i].F;
} else {
result += 1.0 * node[i].J * (M - sum) / node[i].F;
break;
}
}
// System.out.printf("%.3f\n", result);
System.out.println(String.format("%.3f",result));
}
in.close();
}
public static void main(String arg[]){
Main obj = new Main();
obj.solve();
}
}
class Node implements Comparable{
public int J,F;
public double res;
@Override
public int compareTo(Object obj){
Node node = (Node) obj;
if(this.res>node.res) return -1;
else if(this.res<node.res) return 1;
else return 0;
}
}
此题不容易找到正确贪心策略。如果仅仅针对
a
,
b
a,b
a,b进行单独贪心,结果是错的。
我们用常用的寻找贪心策略的方法,如果交换任意两个值,最终的答案都不会更优,则说明之前的贪心策略是对的。
我们假定按照某种排序,前
i
−
1
i-1
i−1 个人的左手之积为
m
m
m , 则第
i
i
i 个人的收益为
t
i
=
m
p
e
r
s
o
n
[
i
]
.
b
t_i = \frac{m}{person[i].b}
ti=person[i].bm
第
i
+
1
i+1
i+1 个人的收益为
t
i
+
1
=
m
∗
p
e
r
s
o
n
[
i
]
.
a
p
e
r
s
o
n
[
i
+
1
]
.
b
t_{i+1} = \frac{m*person[i].a}{person[i+1].b}
ti+1=person[i+1].bm∗person[i].a
现在我们将这两个人交换位置 为了保持一致性,用之前的
i
+
1
i+1
i+1代表此时的
i
i
i
交换之后第
i
i
i 个人的收益为
t
i
′
=
m
p
e
r
s
o
n
[
i
+
1
]
.
b
t_i' = \frac{m}{person[i+1].b}
ti′=person[i+1].bm
交换之后第
i
+
1
i+1
i+1 个人的收益为
t
i
′
=
m
∗
p
e
r
s
o
n
[
i
+
1
]
.
a
p
e
r
s
o
n
[
i
]
.
b
t_i' = \frac{m*person[i+1].a}{person[i].b}
ti′=person[i].bm∗person[i+1].a
此时根据之前的目标,交换之后产生的结果不会比之前的更优。即
m
a
x
(
t
i
,
t
i
+
1
)
<
m
a
x
(
t
i
′
,
t
i
+
1
′
)
max(t_i,t_{i+1})<max(t_i',t_{i+1}')
max(ti,ti+1)<max(ti′,ti+1′)
把公式整理一下,得到
m
a
x
(
p
e
r
s
o
n
[
i
+
1
]
.
b
,
p
[
i
]
.
a
∗
p
[
i
.
b
]
)
<
m
a
x
(
p
[
i
]
.
b
,
p
[
i
+
1
]
.
a
∗
p
[
i
+
1
]
.
b
)
max(person[i+1].b,p[i].a*p[i.b])<max(p[i].b,p[i+1].a*p[i+1].b)
max(person[i+1].b,p[i].a∗p[i.b])<max(p[i].b,p[i+1].a∗p[i+1].b)
此公式即为正确的排序公式。
以下为Java代码 (此代码没有考虑高精度,只能得60分)
/**
*https://vijos.org/p/1779
*@author Hongchuan CAO
*/
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void solve(){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Person[] person = new Person[n+1];
for(int i=0;i<n+1;i++){
person[i] = new Person();
person[i].a = in.nextInt();
person[i].b = in.nextInt();
}
Arrays.sort(person,1,n+1);
double maxx = -1.0;
double sum = 1;
for(int i=0;i<n+1;i++){
if(i==0) {
sum *= person[i].a;
continue;
}else{
maxx = Math.max(maxx,sum/person[i].b);
sum *= person[i].a;
}
}
System.out.println((int)Math.floor(maxx));
}
public static void main(String arg[]){
solve();
}
}
class Person implements Comparable{
public int a,b;
@Override
public int compareTo(Object obj){
Person others = (Person) obj;
int t = Math.max(others.b,this.a*this.b) - Math.max(this.b,others.a*others.b);
if(t>0) return 1;
else if(t<0) return -1;
else return 0;
}
}