您的当前位置:首页正文

贪心专项——训练

2024-11-11 来源:个人技术集锦

HDU-1009

简单贪心 直接从 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 i1 个人的左手之积为 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].bmperson[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&#x27; = \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&#x27; = \frac{m*person[i+1].a}{person[i].b} ti=person[i].bmperson[i+1].a

此时根据之前的目标,交换之后产生的结果不会比之前的更优。即
m a x ( t i , t i + 1 ) &lt; m a x ( t i ′ , t i + 1 ′ ) max(t_i,t_{i+1})&lt;max(t_i&#x27;,t_{i+1}&#x27;) 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 ] ) &lt; 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])&lt;max(p[i].b,p[i+1].a*p[i+1].b) max(person[i+1].b,p[i].ap[i.b])<max(p[i].b,p[i+1].ap[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;
    }

}

Top