题解：P10153 「LAOI-5」膜你赛

· · 题解

思路

由于此题是先按照通过的题目数量不降排序的，所以我们考虑先让过题数量少的选手先走。因此我们会将所有的选手按通过的题目的数量分成很多段，让通过题目数量较少的那一段的选手先走，不难发现由于后面每一段的选手的过题数量相同所以对他们来说并没有影响。

考虑一段内如何安排做题顺序。我们肯定是要让罚时数量比较多的选手先走来避免比前面的选手时间更长。但是这时又出现了一个问题，如果罚时数量较多的选手走了之后，由于他的提交都在比较前面，有可能会导致后面的罚时数量小于等于他的选手花的时间比他长。我们希望使罚时数量小于等于一个选手的最终用时比这个选手的最终用时更短。观察一下数据范围，发现每个选手至少都切了三题。为什么一定要切至少三题呢，我们发现，如果我们让通过数量相同的选手除了最后一次提交，其余的提交都让罚时数量较少的选手先交，就一定可以保证罚时数量少的选手的最终用时小于罚时数量大的选手。因为前面 a_i-1 次提交罚时少的选手拉开罚时多的选手的时间至少是最后一次提交罚时多的选手拉开罚时少的选手的时间的两倍及以上。

于是这题就做完了。

代码

#include<bits/stdc++.h>
#define flush() fwrite(obuf,1,O-obuf,stdout)
#define putchar(x) ((O==obuf+(1<<21))&&(flush(),O=obuf)),*O++=x
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
__inline__ int read(){
    register int x=0;
    register char ch=getchar();
    while(!(ch>='0'&&ch<='9'))
        ch=getchar();
    while(ch>='0'&&ch<='9')
        x=x*10+(ch^48),ch=getchar();
    return x;
}
__inline__ void write(register long long x){
    (x>9)?write(x/10):void();
    putchar((x%10)^48);
}
struct Flush{
    ~Flush(){flush();}
}_;
#define N 100000 + 39
using namespace std;
struct Node
{
    int a, k, id;
}a[N];
int n, m, x;
vector<int>ans,Ans;
inline bool cmp(Node x1, Node x2)
{
    return x1.a == x2.a ? x1.k > x2.k : x1.a < x2.a;
}//按通过数为第一关键字，罚时为第二关键字排序
int main()
{
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    n = read(), m = read(), x = read();
    for(int i = 1; i <= n; i ++)
    {
        a[i].a = read();
    }
    for(int i = 1; i <= n; i ++)
    {
        a[i].k = read();
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    int l = 1, r;
    for(int i = 1; i <= n + 1; i ++)
    {
        if(a[i].a == a[l].a)
        {
            r = i;
        }
        else
        {
            for(int j = r; j >= l; j --)
            {
                for(int k = 1; k < a[l].a; k ++)//对于这一段选手，罚时少的先交
                {
                    ans.push_back(a[j].id);
                    Ans.push_back(0);
                }
            }
            for(int j = l; j <= r; j ++)//最后提交罚时多的先交
            {
                ans.push_back(a[j].id);
                Ans.push_back(a[j].k);
            }
            l = i;
            r = i;
        }
    }
    write(n);
    putchar('\n');
    for(auto it : ans)
    {
        write(it);
        putchar(' ');
    }
    putchar('\n');
    for(auto it : Ans)
    {
        write(it);
        putchar(' ');
    }
    return 0;
}

AC 记录。