1042 Shuffling Machine

题目

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.

The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:

S1, S2, …, S13, H1, H2, …, H13, C1, C2, …, C13, D1, D2, …, D13, J1, J2

where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer K (<= 20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.

Sample Input:
2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47

Sample Output:
S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

思路

题目的意思是，在原先56张纸牌顺序依次排放时，通过输入的次序来对纸牌的摆放进行t次换位。具体的过程可以通过题目中所给的例子来了解。我这题的思路是，将输入的纸牌顺序使用一个order数组来存储，因为我们可能对纸牌进行多次换位，所以这个输入的数组需要记住；而我用card数组来代表对应纸牌当前的顺序，用1到54分别代表54张纸牌。

当读入数组时，card数组也依次赋对应的值，此时相当于进行了第一次换位。随后，在剩余的t-1次中，利用card数组原有的值，在order中查找对应下标对应的值，即为纸牌新的顺序，即card[j] = order[card[j]]。具体代码如下：

#include <iostream>
#include <cstdio>
using namespace std;

void turn(int j){
    if(j >= 1 && j<=13){
        cout << "S" << j;
    }
    else if(j>=14 && j<=26){
        cout << "H" << j-13;
    }
    else if(j>=27 && j<=39){
        cout << "C" << j-26;
    }
    else if(j>=40 && j<=52){
        cout << "D" << j-39;
    }
    else cout << "J" << j-52; 
}

int main(){
    int t;
    cin >> t; 
    int card[55] = {0};
    int order[55];
    for(int i=1; i<=54; i++){
        cin >> order[i];
        card[i] = order[i];
    }
    for(int i=1; i<t; i++){
        for(int j=1; j<=54; j++){ //纸牌,关键 
            card[j] = order[card[j]];
        }
    }
    // for(int i=1; i<=54; i++){cout<<card[i]<<endl;}
    for(int i=1; i<=54; i++){
        for(int j=1; j<=54; j++){
            if(i == card[j] && i!=54){
                turn(j);
                cout << " ";
            }
            else if(i == card[j] && i==54){
                turn(j);
            }
        }
    }
}

本来以为这题自己做不出来，后来认真想想发现其实很简单啦，还是要对自己有信心。另外看了看算法笔记上的题解，感觉还有些麻烦，不如我的做法简单。

1046 Shortest Distance

题目

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:
5 1 2 4 14 9
3
1 3
2 5
4 1
Sample Output:
3
10
7

思路

我的思路很简单，就是把输入的所有距离放在一个数组里。然后再根据之后输入的入口和出口对进行计算，由于要计算两次距离，一次是两个出口之间的直接距离，一次是通过大数折返回小数的距离(环状)
，因此用了三次for循环（后者要用两次）。然后这样导致的问题是，超时。。。代码交上去后，有个测试点过不了，原因就是超时。一开始我以为是我输入输出用了cin和cout，改了之后发现没用。原因如下：

这里借用算法笔记的说法：在极端情况下，每次查询都需要遍历整个数组，即有10^5次操作，而共有10^4次查询，所有会有10^9此操作，这在100ms内无法完成。贴出我的超时代码吧，好歹也有17分（总分20）。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int dis[100005] = {0};
    for(int i=1; i<=n; i++){
        scanf("%d", &dis[i]);
    }
    int t;
    scanf("%d", &t);
    while(t--){
        int x, y;
        scanf("%d%d", &x, &y);
        if(x == y){
            printf("0\n");
        }
        else{
            if(x > y){ //保证前面的大 
                int temp = x;
                x = y;
                y = temp;
            }
            int dis1=0, dis2=0;
            for(int i=x; i<y; i++){
                dis1 += dis[i];
            }   
            for(int i=1; i<x; i++){
                dis2 += dis[i];
            }
            for(int i=y; i<=n; i++){
                dis2 += dis[i];
            }
            printf("%d\n", min(dis1, dis2));
        }       
    }
}

接下来的解法是看算法笔记的。它的思路其实也很直接，并且也很方便。。。哎，我的一开始的思路确实是不太对。傻逼了啊！

记录路程总长度sum，这个变量可以边输入边计算。
以dis[i]表示1号结点按顺时针到达”i号结点顺时针方向的下一个结点”的距离(1<=i<=N)，同样可以边输入边累加。
从left到right的直接距离计算：dist1 = dis[right-1]-dis[left-1]，而另一个方向距离则直接为sum-dist1。

这样做，查询的复杂度就达到O(1)了，真聪明啊！修改后代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int dis[100005] = {0};
    int temp = 0;
    int sum = 0;
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        temp += x;
        sum += x;
        dis[i] = temp; //第1位，储存了1出口和2出口的距离 
    }
    int t;
    scanf("%d", &t);
    while(t--){
        int x, y;
        scanf("%d%d", &x, &y);
        if(x == y){
            printf("0\n");
        }
        else{
            if(x > y){ //保证前面的大 
                int temp = x;
                x = y;
                y = temp;
            }   
            int dis1 = dis[y-1] - dis[x-1];
            int dis2 = sum-dis1;
            printf("%d\n", min(dis1, dis2));
        }           
    }
}

以后还是得注意一下这类问题。