March 2017 CCF Zhenti Solution

1.201703-2

问题描述

体育老师 Xiao Ming wants to line up the students in their class in order. He first asked the students to line up in the order of the student numbers from small to large, with the small student number in front.
Then make multiple adjustments. Adjusting Xiao Ming once may cause a classmate to leave the team and move forward or backward for a distance before inserting into the queue.
For example, the following is an example of a set of moves in which the number of students is eight.
0) The student numbers of the students in the initial queue are 1, 2, 3, 4, 5, 6, 7, 8;
1) For the first adjustment, the order is “No. 3 moves backwards 2”, indicating that the No. 3 class is out of the team, and the distance of the two students is moved backwards, and then inserted into the queue.
The student numbers of the students in the new queue are 1, 2, 4, 5, 3, 6, 7, 8;
2) For the second adjustment, the order is “No. 8 moving forward 3”, indicating that the 8th class is out of the team, moving the distance of 3 students forward, and then inserting into the queue.
The student numbers of the students in the new queue are 1, 2, 4, 5, 8, 3, 6, 7;
3) For the third adjustment, the order is “Class 3 moves forward 2”, indicating that the No. 3 class is out of the team, moving the distance of the two students forward, and then inserting into the queue.
The student numbers in the new queue are 1, 2, 4, 3, 5, 8, 6, 7.
Xiao Ming recorded the process of all adjustments. What is the student number of all the students from the front to the back?
Please note that the numbers involved in the above move process refer to the student number, not the position in the team. When moving backwards, the distance moved does not exceed
Corresponding to the number of students behind the class, if the distance moved backwards is exactly equal to the number of people behind the corresponding classmate, the classmate will move to the end of the queue. When moving forward,
The distance moved does not exceed the number of people in front of the corresponding classmate. If the distance moved forward is exactly equal to the number of people in front of the corresponding classmate, the classmate will move to the front of the queue. 

Input Format

 The first line of the input contains an integer n indicating the number of students, and the student's student number is numbered from 1 to n.
The second line contains an integer m indicating the number of adjustments.
Next m lines, two integers p, q per line, if q is positive, indicating that the student with the student number p moves backward q, and if q is negative, the student with the student number p moves forward -q. 

output format

 outputs a line containing n integers separated by a space between two adjacent integers, indicating the student number of all students from the front to the back. 

样样输入

8
3
3 2
8 -3
3 -2

样样出

1 2 4 3 5 8 6 7

评价用例尺寸和约定

 For all evaluation cases, 1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, all movements are legal. 

考点: Error: Idea:

The first idea AC code:

#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
int ID[MAX],num[MAX];
int m,n;
int Locate(int id)
{
    for(int i=0; i<n; i++)
        if(ID[i]==id) return i;
}

void Back(int a,int b)
{
    int temp,n_count;
    n_count=0;
    a=Locate(a);//7
    temp=ID[a];
    ID[a]=0;
    a=a+b;
    for(int i=0; i<n; i++)
    {
        if(n_count==a)
        {
            num[n_count]=temp;
            n_count++;
            i--;
        }
        else if(ID[i]!=0)
        {
            num[n_count]=ID[i];
            n_count++;
            if(i==n-1&&n_count!=n)
            {
                num[n_count]=temp;
                n_count++;
            }
        }
    }
    for(int i=0; i<n; i++) ID[i]=num[i];
}

void Forward(int a,int b)
{
    int temp,n_count;
    n_count=0;
    a=Locate(a);
    temp=ID[a];
    ID[a]=0;
    a=a-b;
    for(int i=0; i<n; i++)
    {
        if(n_count==a)
        {
            num[n_count]=temp;
            n_count++;
            i--;
        }
        else if(ID[i]!=0)
        {
            num[n_count]=ID[i];
            n_count++;
        }
    }
    for(int i=0; i<n; i++) ID[i]=num[i];

}
int main()
{
    int id,i_move;
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++) ID[i]=i+1;
    while(m--)
    {
        scanf("%d%d",&id,&i_move);
        if(i_move>=0) Back(id,i_move);
        else
        {
            i_move=abs(i_move);
            Forward(id,i_move);
        }
    }
    for(int i=0; i<n; i++) printf("%d ",ID[i]);
    return 0;
}