Transform optimization problems into decision-making problems

Preface

It is a bit similar to the binary search problem , Translate the best answer into , Is there any equal to x Or a better answer .

Travel to Canada

The main idea of the topic
Dongjian decided to drive across Canada . Canadian 1 Highway is one of the longest highways in the world , It connects all major cities from east to West . Dongjian plans to start from the western city of Victoria , Go straight east along the highway , Go to 8030km Outside the eastern city of St. John .
This highway is famous for its numerous road signs ”. Because the highway passes n Major cities , And when we are about to reach a city , The number of road signs indicating the remaining distance is very large . Marked with a distance of i How far is the road sign of the city from before it arrives Mi Rice starts , With Gi Meter interval is set .

int n,k;
int l[5000],m[5000],g[5000];
// Decision making issues , arrive dist  Can encounter k More than road signs 
bool decision(int dist){
    
    int ret = 0;
    for(int i=0;i<n;++i){
    
        // Can meet  1 More than i The road signs of a city 
        if(dist >= l[i]-m[i])
        ret += (min(dist,l[i]) - (l[i]-m[i]))/g[i] + 1;
        return ret>= k;
    }
}

// Computation first k Location of road signs 
int optimize(){
    
    // Cyclic inequality ： ！decision(lo)&& decision(hi)
    int lo = -1,hi = 80300001;
    while(lo+1 < hi){
    
        int mid = (lo + hi)/2;
        if(decision(mid))
        hi = mid ;
        else lo = mid;
    }
    return hi;
}

Drop out course

The main idea of the topic
Bojun blindly chose more courses this semester , The result exceeded the credits . After getting the midterm grades , Because the grades did not meet the criteria for obtaining scholarships next semester , There is only one sigh left . Now? , He can only seize the opportunity to withdraw from the course starting next week .
The school will allocate scholarships according to the ranking after the mid-term and final exams . for example , A student chooses the first 1 There are courses c： Students attend classes . If this student's first i The mid-term ranking of courses is Ii,
that , The cumulative ranking of the student's mid-term exam will be defined as the following form .
$$\frac{{\sum }_{}{r}_i}{{\sum }_{}{c}_i}$$
If you drop out of the course , Then the withdrawn subjects will not be included in the cumulative ranking of the mid-term exam . School rules , Even if you drop out of the course , As long as the remaining courses exceed k individual , You can get scholarships according to the ranking . When Bo Jun withdraws from the course appropriately , Try to write a program to calculate the minimum cumulative ranking he can get .

Their thinking

Convert to decision(x) = Withdrawing courses appropriately can reduce the cumulative ranking to x The following
Turn into $$\frac{{\sum }_{}{r}_i}{{\sum }_{}{c}_i}<=x$$
Finishing becomes
$$0<=x\sum c_i-\sum r_i=\sum (x{c}_i-r_i)$$

int n,k;
int c[N],r[N];
// Decision making issues , Can the cumulative ranking be changed into  average

bool decision(double average){
    
    vector<double>v;
    for(int i=0;i<n;++i)
    v.push_back(average*c[i] - r[i]);
    sort(v.begin(),v.end());
    // Turn this question into  ‘v in k Can the sum of the elements be greater than 0’ The problem of , Then use greedy methods to solve 
    double sum  = 0;
    for(int i = n-k;i<n;++i)
    sum += v[i];
    return sum >= 0;
}

// optimization problem , Calculate the minimum cumulative ranking that can be accumulated 
double optimiza(){
    
    //  The cumulative ranking is  [0,] The real number between 
    //  Cyclic infinitive 
    double lo = -1e9 ,hi = 1;
    for(int iter = 0;iter<100;iter++){
    
        double mid = (lo + hi)/2;
        // Can you reach the cumulative ranking mid
        if(decision(mid))
        hi = mid;
        else
        lo = mid;
    }
    return hi;
}