sharepoint是什么-金山卫士手机版
2023年4月3日发(作者：winiso下载)
对于100%的数据，1≤N≤100,000，1≤R≤50，1≤Q≤2N，0≤s1,s2,…,s2N
≤10^8，1≤w1,w2,…,w2N≤10^8。
这个数据告诉我们：使用快速排序只能拿到50-60分。可是我却把它直接忽略了。
（不知道怎么回事，我写了快速排序只拿到了10分，后面的40分莫名其妙丢掉了，不知道
为什么。）
现在我是C++的OIER，所以就直接使用C++的sort函数（sort当然不能AC50分）。
我在vijos50分的代码：
#include
#include
#include
#include
#include
#include
usingnamespacestd;
structsportsman
{
intid,score,power;
}V[200005];
intN,R,Q;
voidstart_contest()
{
for(inti=1;i<=N;i+=2)
if(V[i].power>V[i+1].power)
V[i].score++;
else
V[i+1].score++;
}
boolcompare(sportsmana,sportsmanb)
{
if(==)
<;
else
>;
}
intmain()
{
//freopen("","r",stdin);
scanf("%d%d%d",&N,&R,&Q);
N*=2;
for(inti=1;i<=N;i++)
{
V[i].id=i;
intscore;
scanf("%d",&score);
V[i].score=score;
}
for(inti=1;i<=N;i++)
{
intpower;
scanf("%d",&power);
V[i].power=power;
}
sort(V+1,V+N+1,compare);
for(inti=1;i<=R;i++)
{
start_contest();
sort(V+1,V+N+1,compare);
}
printf("%dn",V[Q].id);
return0;
}
然后我就想到了优化最后一轮比赛（调用nth_element函数优化）
不过根本也没有优化多少，还是50分。与原通过数据比起来，优化63ms
代码：
#include
#include
#include
#include
#include
#include
usingnamespacestd;
structsportsman
{
intid,score,power;
}V[200005];
intN,R,Q;
voidstart_contest()
{
for(inti=1;i<=N;i+=2)
if(V[i].power>V[i+1].power)
V[i].score++;
else
V[i+1].score++;
}
boolcompare(sportsmana,sportsmanb)
{
if(==)
<;
else
>;
}
intmain()
{
//freopen("","r",stdin);
scanf("%d%d%d",&N,&R,&Q);
N*=2;
for(inti=1;i<=N;i++)
{
V[i].id=i;
intscore;
scanf("%d",&score);
V[i].score=score;
}
for(inti=1;i<=N;i++)
{
intpower;
scanf("%d",&power);
V[i].power=power;
}
sort(V+1,V+N+1,compare);
for(inti=1;i<=R;i++)
if(i!=R)
{
start_contest();
sort(V+1,V+N+1,compare);
}
else
{
start_contest();
nth_element(V+1,V+Q,V+N+1,compare);
printf("%dn",V[Q].id);
}
return0;
}
最后实在是想不出对源程序的优化了。憋了很久，终于想出了一个归并的优化（AC，基于
STLalgorithmmerge函数）：
首先，还是要使用sort对N*2个选手进行排序（我重载比较符号，来实现选手之间的大小），
注意：只进行一轮！
然后，我们开两个vector，分别记录失败者和胜利者信息，最后我们调用STLalgorithmmerge
函数将这两个vector合并到一个result容器中就行了。
为什么这个方法行的通？如果两个选手的分数相同，编号小的要排在前面，怎么做到呢？
我们可以再来想一下归并排序，归并排序是一个稳定的排序（相当与stable_sort），所以merge
函数可以保证原来选手位置的相对顺序！（只可惜我这次NOIP的语言不是C++。）
再来比较一下使用sort函数merge函数的时间复杂度：
sort函数：很明显：O(NlogN*R)
merge函数：合并一轮是O(n)的复杂度，所以复杂度就是：O(Rn)。这个算法显然可以通过，
N假设是10万，R假设是50，也不过是进行了500万次操作，1秒钟肯定可以通过最强数
据。
最后我们只要输出result[Q].idnum就行了。
代码：
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
structsportsman
{
intid,score,power;
booloperator>(constsportsman&t)const
{
if(==score)
returnid<;
else
returnscore>;
};
}result[200005];
vector
intN,R,Q;
voidstart_contest()
{
for(inti=0;i
{
if(result[i].power>result[i+1].power)
{
result[i].score++;
_back(result[i]);
_back(result[i+1]);
}
else
{
result[i+1].score++;
_back(result[i+1]);
_back(result[i]);
}
}
}
intmain()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
intscore,power;
scanf("%d%d%d",&N,&R,&Q);
N*=2;
for(inti=0;i
{
scanf("%d",&score);
result[i].id=i+1;
result[i].score=score;
}
for(inti=0;i
{
scanf("%d",&power);
result[i].power=power;
}
sort(result,result+N,greater
for(inti=0;i
{
start_contest();
merge((),(),(),(),result,greater
();
();
}
printf("%dn",result[Q-1].id);
return0;
}
评测结果：
#01:Accepted(0ms,2688KB)
#02:Accepted(0ms,2688KB)
#03:Accepted(0ms,2692KB)
#04:Accepted(0ms,2948KB)
#05:Accepted(0ms,3196KB)
#06:Accepted(53ms,3692KB)
#07:Accepted(193ms,4624KB)
#08:Accepted(443ms,6548KB)
#09:Accepted(521ms,6548KB)
#10:Accepted(631ms,6548KB)
Accepted/100/1843ms/6548KB
可见，前5个数据0ms秒杀，后面的数据所花费的时间逐渐递升，至少时间都控制在600ms
左右。
更多推荐
noip2011
发布评论