题目：处女座挑选了n道题开始刷，自己没有解决的题目每分钟都会给他带来bi的疲倦值，而解决每一道题目都需要花费ai分钟的时间。当然，处女座一般都是考虑清楚了再写题的，所以他在写题的时候都会精神抖擞，也就是说，当前正在写的那一题并不会给他带来任何疲劳。
找出最小所需要的疲倦值。
ps：（2≤N≤105).(2≤ai≤4*106).(1≤bi≤1000）
#include <stdio.h> #include <algorithm> using namespace std; typedef struct ti { long a; int b; }ti; ti arr[1000050]; bool cmp(ti A,ti B) { return (A.a*1.0)/A.b<(B.a*1.0)/B.b ; //性价比排序 } int main() { long n; long long sum = 0; long long ans = 0; scanf("%d",&n); for(long i = 0;i < n;i++) { scanf("%d %d",&arr[i].a,&arr[i].b); sum += arr[i].b; } sort(arr,arr+n,cmp); for(long j = 0;j < n;j++) { sum -= arr[j].b; ans += sum * arr[j].a; } printf("%lld",ans); return 0; }
思路：
我一开始的【错误思路】就是按照疲惫值由大到小排序，如果疲惫值一样，就按照做题时间由小到大排序。在依次计算求和即可。（但是当如果示例为 9/11 ； 10 /11 ; 2/8 的时候就发现按照比值排序的疲惫值更小）
但是这道题用的是【正确思路】性价比排序（比值？:用时间/疲惫值从大到小排序）……（类似于背包按单位体积价值排序？？）
