这道题网上很多人都会说容易，水题之类的话，不过我看了下说这样的话的人的程序，可以说他们的程序都不及格！

为什么呢？因为他们的程序都是使用简单的二次排序水过（大概你能搜索到的多是这样的程序），那样自然可以说不及格了。

因为本题真正的目的是求前k个最大数的问题，这就需要活用快速排序。

求前k个最大数的思路：

1 选取一个数位轴，然后把大于这个数的数放到数列前面，小于这个数的数放到数列后面

2 如果前面的数的数量大于k，那么可以去掉后面的数，递归在前面的数查找前k个最大数

3 如果前面的数的数量小于k，那么截去前面的数的数量，即k减去这些数量，然后在后面数列查找

4 如果前面的数刚好等于这个k，那么就可以返回了，找到前k个大数了。

然后主要是要注意细节问题，下标没计算好，会浪费很多调试时间的。

?

最后AC的程序：

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; struct TripNums { int a, b, i; }; void seleteK(vector
     
       &vtri, int l, int r, int k) { vector
      
        fro, bac; int val = vtri[r].a; for (int i = l; i < r; i++) { if (vtri[i].a < val) bac.push_back(vtri[i]); else fro.push_back(vtri[i]); } int i = l; for (int j = 0; j < (int)fro.size(); j++) { vtri[i++] = fro[j]; } vtri[i++] = vtri[r]; if ((int)fro.size() == k || (int)fro.size()+1 == k) return ; if ((int)fro.size() > k) { seleteK(vtri, l, l + (int)fro.size()-1, k); return ; } for (int j = 0; j < (int)bac.size(); j++) { vtri[i++] = bac[j]; } seleteK(vtri, l + (int)fro.size() + 1, r, k - (int)fro.size() - 1); } int main() { int N, K; while (~scanf(%d %d, &N, &K)) { vector
       
         vtri(N); for (int i = 0; i < N; i++) { scanf(%d %d, &vtri[i].a, &vtri[i].b); vtri[i].i = i; } seleteK(vtri, 0, N-1, K); int idx, M = INT_MIN; for (int i = 0; i < K; i++) { if (vtri[i].b > M) { idx = vtri[i].i; M = vtri[i].b; } } printf(%d , idx+1); } return 0; }
       
      
     
    
   
  

?

?