ALGO-973 唯一的* 蓝桥杯题解

ALGO-973 唯一的*

资源限制

时间限制:1.0s 内存限制:256.0MB

问题描述

腿铮找2255有点事,但2255太丑了,所以腿铮不知道他的长相。正愁不知道到如何找他的时候,他突然看见计33班围成了一个圈在领微积分试卷。计33班有n个人,其中班长编号为0,其余同学依次按顺时针方向编号。
  只听见计33小导说“x号同学顺时针方向往后数的第k个的神犇出列(不包括x号同学),领取满分试卷!”。剩下的人继续围成一个小圈。这样一个过程持续了n-1次,那么显然,最后只剩下了一个人。众所周知,2255是个大*,门门挂科,不符合满分试卷这一前提条件。通过这样一个过程,腿铮终于找到了2255并血虐了他。
  求2255的编号是多少。

输入格式

第一行一个n,表示计33班的人数。
  接下来n-1行,表示小导说话中的x和k。

输出格式

一个数字,表示2255的编号。

样例输入

3
1 1
0 1

样例输出

0

数据规模和约定

前90%数据保证n<=10^4.
  前100%数据保证n<=10^6,1<=k<min(当时圈中人数,1000)

分析用链表做一个地址等于链表下表的环,从而不需要存元素,只需要存地址,然后找到要删除的元素前一个元素删掉该元素即可

比如x号同学的地址为x,他的下一个就是ne[x],本来应该有个e去存这个同学叫什么的,但是既然是先沟通的就不用存这个x了就直接存x的下个人是谁就可以了

时间复杂度为O(n * 1000) 大约要算10^7次, 肯定小于10^8次,所以1s内可以算完

#include <iostream>

using namespace std;

const int N = 1000010;

int L, ne[N], t;//L为当前环的长度,ne链表的next指针

void del(int x, int k)
{
    t = x;
    for (int cnt = 0; cnt == k % L; t = ne[t], cnt ++ );//每次遍历到要删除的节点的前一个节点
    ne[t] = ne[ne[t]];//当L只有2的时候t为最终留下来的那个节点的地址
    L -- ;
}

int main()
{
    int n;
    scanf("%d", &n);
    L = n;
    for (int i = 0; i < n; i ++ )//初始化环,这里是形如0->1->2->3->0的一个地址等于元素值的环
    {
        ne[i] = (i + 1) % n;
    }
    for (int i = 1; i < n; i ++ )
    {
        int x, k;
        scanf("%d%d", &x, &k);
        del(x,k);
    }
    cout << t;
    return 0;
}
上一篇:第7章第33节:五图排版:错落有致的波浪式排版 [PowerPoint精美幻灯片实战教程]


下一篇:常用内置函数