专栏首页饶文津的专栏【校赛小分队之我们有个女生】训练赛6

【校赛小分队之我们有个女生】训练赛6

题意

每个manager给数组a的第1到r[i]个数排序,t[i]==1则排升序,2则排降序。求m个manager排序完的序列。

分析

如果之前的r比较小,肯定会被更大的r的操作覆盖掉,所以我们要找到r的递减序列。 先找出最大的r,然后在这个r的后面再找最大的r,循环这样,找出了一个r的递减的序列,然后再模拟排序。

但是最坏情况:【r刚好从最大到最小,这样每次都要排一下序】时间复杂度mlogm+m*nlogn,会超时。

改成填数复杂度就变成mlogm+n,填数就是先给a的最大的r之前的数排个序,最大的r到第二大之间,如果是升序,那就把a大的那一头填进去,如果是降序,就把小的那一头填进去。以此类推前面的区间。

不过我找r的递减序列时出错了:只要id大于刚刚的manager的id(出现得更迟),并且排序方法不一样就让这个manager排一下。

int j=1;
solve(j);//第j个(按r排)manager来排a
for(int i=2; i<=m; i++)
{
    if(b[i].id>b[j].id&&b[i].t!=b[j].t)
    {
        solve(i);
        j=i;
    }
}

wa在test 14,但是因为太长,没法看到完整的数据,所以自己造数据,终于找出错在哪了,一个反例:

9 3
1 2 3 4 5 6 7 8 9
2 9
1 4
2 6

n=9,m=3 r:9 4 6 t:2 1 2 我的程序会先排9,升序,然后因为6升序,所以不排,于是j没有更新为6,然后排4,降序,这样就错了,因为4其实在6之前出现,所以应该忽略。 循环里改为这样就好了:

if(b[i].id>b[k].id)
{
    if(b[i].t!=b[j].t)
    {
        r[cnt++]=i;
        j=i;
    }
    k=i;
}

k就是上一个排序的id,如果现在这个id大,就是后面的manager,现在的排法和前一个记录在r序列里的不一样,就记录进去。

代码

#include<cstdio>
#include<algorithm>
#define N 200005
using namespace std;
int n,m,a[N],c[N],r[N];
struct mng
{
    int r,t,id;
} b[N];
int cmp(mng a,mng b)
{
    return a.r>b.r;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&b[i].t,&b[i].r);
        b[i].id=i;
    }
    sort(b+1,b+1+m,cmp);//manager按r排降序
    int j=0,k=0,cnt=0;
    //筛选出r递减的manager序列
    for(int i=1; i<=m; i++)
    {
        if(b[i].id>b[k].id)
        {
            if(b[i].t!=b[j].t)
            {
                r[cnt++]=i;
                j=i;
            }
            k=i;
        }
    }
    for(int i=b[1].r+1; i<=n; i++) c[i]=a[i];
    sort(a+1,a+1+b[1].r);//a数组b[1].r前的排升序
    int tou=1,wei=b[1].r;
    for(int i=0; i<cnt; i++)
        if(b[r[i]].t==2)//当前的第r[i]个manager要降序
            for(int j=b[r[i]].r; j>b[r[i+1]].r; j--) //小的从右到左放过去
                c[j]=a[tou++];
        else
            for(int j=b[r[i]].r; j>b[r[i+1]].r; j--)
                c[j]=a[wei--];//大的从右到左放过去
    for(int i=1; i<=n; i++)
        printf("%d ",c[i]);
    return 0;
}

B.没看

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【USACO 3.1】Contact(01子串按出现次数排序)

    题意:给你一个01字符串,将长度为a到b之间(包含a、b)的子串按照出现次数排序。注意输入输出格式

    饶文津
  • 【HDU 5855】Less Time, More profit(网络流、最小割、最大权闭合子图)

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Othe...

    饶文津
  • 「AtCoder Grand018A」Getting Difference(GCD)

    有n(1~\(10^5\))个数\(A_i\) (110^9),每次选两个数,将它们的差的绝对值加入这堆数。问k(1\(10^9\))是否可能出现在这堆数中。

    饶文津
  • 洛谷P1081 开车旅行(倍增)

    \(da[i][j]\)同理表示\(a\)的距离,\(db[i][j]\)与\(da\)同理

    attack
  • mybatis 详解(七)------一对一、一对多、多对多

      前面几篇博客我们用mybatis能对单表进行增删改查操作了,也能用动态SQL书写比较复杂的sql语句。但是在实际开发中,我们做项目不可能只是单表操作,往往会...

    IT可乐
  • pageadmin CMS网站建设:信息表内容页数据调用及相关方法

    pageadmin CMS网站制作:信息表内容页数据调用及相关方法 1、信息表内容调用语法

    Almost Lover
  • 、Maximum Product Subarray

    Find the contiguous subarray within an array (containing at least one number) wh...

    Tyan
  • 牛客练习赛23 D

      利用全排列函数加vector数组,开十个vector,存a到i字母出现的位置,最后每个vector再push_back(字符串长度加一)作为结束标志。

    用户2965768
  • 纸上谈兵: 排序算法简介及其C实现

    排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

    Vamei
  • 46. 全排列【回溯算法】

    输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...

    韩旭051

扫码关注云+社区

领取腾讯云代金券