认真读题很重要
简单分析
题目链接:[https://www.luogu.org/problemnew/show/P1309]很容易发现,这道题目考察的排序,排序我们第一个肯定想到的是sort或者是归并排序,的确时间复杂度分别是
O(n log2(n) )
与O(n log(n) )
可如果是多次计算呢? 排除快排是因为不稳定性
所以总时间复杂度约为: sort O( r*2n^2*log2(2n) )
归并 O( r*2n^2*log(2n) )
看看数据范围emmmm 据说这样会 60 分,剩下的你懂的
所以我们需要优化
很显然sort
已经没有优化的余地了,所以我们要从归并考虑
然后我们发现每次增减分的数组是单调的
也就是说我们只需要在开始的时候全部排序,后面我们每次只需要花O(n)
的时间合并即可
这样子的时间复杂度约为:O( r*n^2 )
稳如老狗啊!!!
代码
#include <cstdio>
#include <algorithm>
using namespace std;
int n,r,q;
struct node {
int n,s,p;// n 号码 s 分数 p 能力
}a[210000],left[110000],right[110000];
int lcnt,rcnt,cnt,result_start;
// cmp 不解释
bool cmp(node a,node b){
if(a.s==b.s) return a.n<b.n;
else return a.s>b.s;
}
// 合并区间,参照归并排序
void marge(int left_start,int right_start){
result_start=1;
while(left_start<=n&&right_start<=n){
if(cmp(left[left_start],right[right_start])) a[result_start++]=left[left_start++];
else a[result_start++]=right[right_start++];
}
while(left_start<=n) a[result_start++]=left[left_start++];
while(right_start<=n) a[result_start++]=right[right_start++];
}
int main(){
// 读入
scanf("%d%d%d",&n,&r,&q);
for(int i=1;i<=2*n;i++){scanf("%d",&a[i].s);a[i].n=i;}
for(int i=1;i<=2*n;i++) scanf("%d",&a[i].p);
sort(a+1,a+1+2*n,cmp);
for(int i=1;i<=r;i++){
lcnt=rcnt=0;// 模拟比赛过程
for(int j=1;j<=2*n;j+=2){
if(a[j].p>=a[j+1].p){
a[j].s+=1;
//printf("%d\n",++cnt);
left[++lcnt]=a[j];right[++rcnt]=a[j+1];
}
else{
a[j+1].s+=1;
//printf("%d\n",++cnt);
right[++rcnt]=a[j];left[++lcnt]=a[j+1];
}
}// 排序不解释
if(i==1) sort(a+1,a+1+2*n,cmp);
else marge(1,1);
}
printf("%d",a[q].n);
}
End
灵活运用每一种算法是一个非常重要的艺术 ]]>