poj 2976 Dinkelbach迭代法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn = 1005;
struct node{
    double a,b,c;
}Node[maxn];

//double a[maxn],b[maxn],c[maxn],d[maxn];
int m,n,k;
double mid;

int cmp(const void *i,const void *j){
    return (*(struct node *)i).c < (*(struct node *)j).c ? 1 : -1;
}
int main()
{
    //if(freopen("input.txt","r",stdin)== NULL)  {printf("Error\n"); exit(0);}
    while(cin>>n>>k && n){
         m = n - k; 
        for(int i=0;i<n;i++) cin>>Node[i].a;
        for(int i=0;i<n;i++) cin>>Node[i].b;
        
        double p=0.5;
        while(true){
            for(int i=0;i<n;i++) Node[i].c = Node[i].a - p * Node[i].b;
            
            qsort(Node,n,sizeof(struct node),cmp);  
            double q = 0.0,suma=0.0,sumb=0.0;
            for(int i=0;i<m;i++){
                suma += Node[i].a;
                sumb += Node[i].b;
            }
            q = suma / sumb;
            if( abs(q-p) < 1e-5) { mid = q; break;}
             else p = q;
        }
        
        int ans =  floor(100 * mid+0.5);
        printf("%d\n",ans);
    }
    return 0;
}