UVA_10026

这个是一个贪心的题目首先按照fine/time降序排列，值相同的再按序号升序排列。

对于为什么贪心策略是这个样子的，我们不妨拿相邻的两个事件a、b来说明一下。由于a、b之后的事件是固定的，所以我们无论排成ab还是排成ba后面部分的损失都是固定的，那么损失的差别主要来源于究竟是排成ab还是排b成a。排ab的损失为ta*fb，排ba的损失为tb*fa，那么如果ta*fb<tb*fa，我们就排成ab，这样可以得到fa/ta>fb/tb，推而广之，就得到了我们的贪心策略。

#include
     
       #include
      
        #include
       
         double time[1010],fine[1010],b[1010]; int r[1010]; int cmp(const void *_p,const void *_q) {
   int *p=(int *)_p; int *q=(int *)_q; if(fabs(b[*p]-b[*q])<1e-6) return *p-*q; else if(b[*p]