Problem Statement
There is an empty array. The following N operations will be performed to insert integers into the array. In the i-th operation (1≤i≤N), bi copies of an integer ai are inserted into the array. Find the K-th smallest integer in the array after the N operations. For example, the 4-th smallest integer in the array {1,2,2,3,3,3}is 3.
Constraints
- 1≤N≤105
- 1≤ai,bi≤105
- 1≤K≤b1…+…bn
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N K a1 b1 : aN bN
Output
Print the K-th smallest integer in the array after the N operations.
Sample Input 1
3 4 1 1 2 2 3 3
Sample Output 1
3
The resulting array is the same as the one in the problem statement.
Sample Input 2
10 500000 1 100000 1 100000 1 100000 1 100000 1 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
Sample Output 2
1
思路:用结构体排序讲a先从小到大排一边,然后再挑选出只要b的总合大于K的结构体然后输出就行
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; struct str { long long p,q; }a[N]; bool cmp( str x, str y) //结构体排序按a的值从小到大排 { return x.p<y.p; } int main() { long long m,n,i; cin>>m>>n; for(i = 0; i < m; i++){ cin>>a[i].p>>a[i].q; } sort(a,a+m,cmp); long long sum = 0; for(i = 0; i < m; i++){ sum += a[i].q; if(sum >= n){ //挑选出符合条件的然后输出 cout<<a[i].p<<endl; break; } } return 0; }