DTOJ 2825: 赛车比赛(race)

2825: 赛车比赛(race)
时间限制: $2 Sec$2Sec 内存限制: $256 MB$256MB $O2$O2

题目描述
$USB$USB自己做了一辆卡丁车去参加$f1$f1赛事，经过了一轮预选赛，还剩下$n$n名选手进入决赛。

由于各选手的预赛成绩不同，所以各选手的出发点$s_{i}$si​也是根据成绩而定的，有些人的出发点不同，有些人出发点相同。每位选手根据状态还有一个保持不变的速度$v_{i}$vi​。为了简化问题，设跑道为一条数轴，选手的坐标即为其通过距离。

排名方法如下，如果一辆车在另一辆车前面，则这辆车在另一辆车前。如果两车的通过距离相同，则编号小的在前。

$USB$USB的卡丁车是世界一流的，他不用担心当不了第一名。他现在想知道，第$t$t时刻排在第$k$k位的是那辆车。

输入
第一行，包含一个正整数$n$n。

第$2$2~$n+1$n+1行，第$i+1$i+1行包括两个正整数$v_{i}，s_{i}$vi​，si​。

第$n+2$n+2行，包含一个正整数$m$m。

第$n+3$n+3~$m+2$m+2行，每行表示一个询问，包括两个正整数t,k。

输出
输出包括$m$m行，每行表示每个询问时刻$t$t排在第$k$k位的选手编号。

样例输入
4
2 100
3 50
4 60
5 1
4
1 1
50 2
60 4
100 1
样例输出
1
4
1
4
提示
【数据规模与约定】

对于$30\%$30%的数据：$n,m≤1000;$n,m≤1000;

另有$40\%$40%的数据：$k=1;$k=1;

对于$100\%$100%的数据: $n,m≤7000;t≤1,000,000,000;v,s≤100,000;k≤n.$n,m≤7000;t≤1,000,000,000;v,s≤100,000;k≤n.

题解：
emmmmmm。。。。。网上有一种炒鸡强的写法，叫做冒泡排序，但是我不会。。。。
于是，万能的$STL$STL 助我切掉这题，赐予了我一个工具，叫$nth\_\ element$nth_ element
对于每个询问，先找到前$k$k大的放前面，再找到前$k-1$k−1的放前面，就好了。

#include<bits/stdc++.h>
using namespace std;
#define in inline
#define re register
#define rep(i,a,b) for(re int i=a;i<=b;i++)
#define _(d) while(d(isdigit(ch=getchar())))
template<class T>in void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
typedef long long ll;
const int N=7004;
int n,m;
struct A{ll v,s,d,id;}a[N];
in bool cmp(A x,A y){return x.d>y.d||(x.d==y.d&&x.id<y.id);}
int main(){
	g(n);
	rep(i,1,n) g(a[i].v),g(a[i].s),a[i].id=i;
	g(m);
	rep(i,1,m){
		ll t,k;g(t),g(k);
		rep(j,1,n) a[j].d=a[j].v*t+a[j].s;
		nth_element(a+1,a+1+k,a+1+n,cmp);
		nth_element(a+1,a+k,a+1+k,cmp);
		printf("%lld\n",a[k].id);
	}
	return 0;
}