【C++】洛谷P1309瑞士轮

不会手写归并排序但想用STL尽量得部分分

先用sort做一遍

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string> 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
const int N=200005;
int read()//日常快读... 
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node
{
    int id;//编号 
    int w;//实力值 
    int sx;//初始值,之后会不断更新 
}q[N];
bool cmp(const node &a,const node &b)
{
    if(a.sx!=b.sx) 
        return a.sx>b.sx;
    else 
        return a.id<b.id;
}
int n,r,Q;
int main(int argc, char** argv) {
    int i,j;
    n=read(); r=read(); Q=read();
    for(i=1;i<=2*n;i++)
    {
        q[i].sx=read();
        q[i].id=i;
    }
    for(i=1;i<=2*n;i++)
        q[i].w=read();
    sort(q+1,q+2*n+1,cmp);//开始要先排一遍 

    for(i=1;i<=r;i++)//这里就是纯模拟了 
    {
        for(j=1;j<=2*n;j=j+2)
        {
            if(q[j].w>q[j+1].w) q[j].sx++;
            else q[j+1].sx++;
        }
        sort(q+1,q+2*n+1,cmp);
    }
    printf("%d",q[Q].id);//printf比cout快的 
    return 0;
}

60分....

这主要是因为sort实质是快速排序(二分),相邻两个人分数变化后,有时是不会改变位置的，但快速排序是每次全部修改,所以造成浪费 但是开o2能过

然后介绍一个实质是归并排序的STL,它就是stable_sort 可以说stable_sort和sort的用法一样,而没多少人知道是因为大部分时候sort就可以解决很多问题,只要把上述代码中的sort全部改成stable_sort就能得80分了。