题目描述

A Ministry for Defense sent a general to inspect the Super Secret Military Squad under the command of the Colonel SuperDuper. Having learned the news, the colonel ordered to all n squad soldiers to line up on the parade ground.

By the military charter the soldiers should stand in the order of non-increasing of their height. But as there’s virtually no time to do that, the soldiers lined up in the arbitrary order. However, the general is rather short-sighted and he thinks that the soldiers lined up correctly if the first soldier in the line has the maximum height and the last soldier has the minimum height. Please note that the way other solders are positioned does not matter, including the case when there are several soldiers whose height is maximum or minimum. Only the heights of the first and the last soldier are important.

For example, the general considers the sequence of heights (4, 3, 4, 2, 1, 1) correct and the sequence (4, 3, 1, 2, 2) wrong.

Within one second the colonel can swap any two neighboring soldiers. Help him count the minimum time needed to form a line-up which the general will consider correct.

Input
The first input line contains the only integer n (2 ≤ n ≤ 100) which represents the number of soldiers in the line. The second line contains integers a1, a2, …, an (1 ≤ ai ≤ 100) the values of the soldiers’ heights in the order of soldiers’ heights’ increasing in the order from the beginning of the line to its end. The numbers are space-separated. Numbers a1, a2, …, an are not necessarily different.

Output
Print the only integer — the minimum number of seconds the colonel will need to form a line-up the general will like.

样例

Examples

input
4
33 44 11 22
output
2

input
7
10 10 58 31 63 40 76
output
10

---------------------------------------
Note

In the first sample the colonel will need to swap the first and second soldier and then the third and fourth soldier. That will take 2 seconds. The resulting position of the soldiers is (44, 33, 22, 11).

In the second sample the colonel may swap the soldiers in the following sequence:

(10, 10, 58, 31, 63, 40, 76)
(10, 58, 10, 31, 63, 40, 76)
(10, 58, 10, 31, 63, 76, 40)
(10, 58, 10, 31, 76, 63, 40)
(10, 58, 31, 10, 76, 63, 40)
(10, 58, 31, 76, 10, 63, 40)
(10, 58, 31, 76, 63, 10, 40)
(10, 58, 76, 31, 63, 10, 40)
(10, 76, 58, 31, 63, 10, 40)
(76, 10, 58, 31, 63, 10, 40)
(76, 10, 58, 31, 63, 40, 10)

题目翻译：
一个国防部派了一位将军来视察超级秘密军事小队，由SuperDuper上校指挥。得知这一消息后，上校命令所有N个小队的士兵在阅兵场上列队。

根据军事章程，士兵们应该按照身高不增加的顺序站立。但由于几乎没有时间，士兵们按照任意的顺序排队。然而，将军是个短视的人，他认为如果队伍中第一个士兵的身高最大，最后一个士兵的身高最小，那么士兵们的排队就正确了。请注意，其他士兵的排列方式并不重要，包括有几个士兵的高度是最大或最小的情况。只有第一个和最后一个士兵的高度是重要的。

例如，将军认为高度顺序（4，3，4，2，1，1）正确，顺序（4，3，1，2，2）错误。

在一秒钟内，上校可以调换任何两个相邻的士兵。请帮助他计算出形成将军认为正确的阵容所需的最少时间。

输入
第一行输入的是唯一的整数n（2≤n≤100），代表队伍中士兵的数量。第二行包含整数a1, a2, …, an (1 ≤ ai ≤ 100)，代表士兵的高度，按士兵的高度从行首到行尾的顺序递增。这些数字是以空格分隔的。数字a1，a2，…，an不一定不同。

输出
打印唯一的整数–上校形成将军喜欢的阵容所需的最小秒数。

算法1

模拟

找出最靠右的最小值下标和最靠左的最大值下标。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int a[110];
int mins=110,maxs=0,imin,imax;

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] > maxs)
        {
            maxs = a[i];
            imax = i;
        }
    }

    for (int i = n; i >= 1; i -- )
    {
        if (a[i] < mins)
        {
            mins = a[i];
            imin = i;
        }
    }

    int ans = imax - 1 + n - imin; //ans = 往左移次数+往右移次数

    if (imax > imin) cout << ans - 1 << endl; //两者在移动过程中有交换，则答案数-1
    else cout << ans << endl; //否则直接输出即可

    return 0;
}

题目描述

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0 ∼ n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

数据范围
0≤n≤1000

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

算法1

另开一个数组存每个数字出现的次数即可，注意特判。

C++ 代码

class Solution {
public:
    int cnt[1010] = {0};
    int duplicateInArray(vector<int>& nums) {

        int n = nums.size();

        for (auto i : nums)
        {    
            if (i < 0 || i >= n)
            return -1;
        }

        for (int i = 0; i < n; i ++ )
        {
            if (nums[i] >= 0) cnt[nums[i]] ++;
        }

        for (int i = 0; i < n; i ++ )
        {
            if (cnt[i] > 1) return i;
        }

        return -1;
    }
};

题目描述

输入两个非负 10 进制整数 A 和 B (≤ 2^30 −1)，输出 A+B 的 D (1<D≤10)进制数。

输入格式：
输入在一行中依次给出 3 个整数 A、B 和 D。

输出格式：
输出 A+B 的 D 进制数。

样例

输入样例：
123 456 8

输出样例：
1103

算法1

递归

注意特判0

C++ 代码

#include <bits/stdc++.h>

using namespace std;

char a[] = {'0','1','2','3','4','5','6','7','8','9','A'};

void d_to(int x, int m)
{
    if (x==0) return; //递归出口
    d_to(x/m,m);
    cout << a[x%m]; //输出余数
}

int main()
{
    int a,b,m;
    cin >> a >> b >> m;

    int x = a + b;

    if (x == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    d_to(x,m);

    cout << endl;

    return 0; 



}

题目描述

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (≤10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式：
每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

样例

输入样例：
10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA

输出样例：
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

模拟

红温

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    while (n--)
    {
        string s;
        cin >> s;

        bool ans = true;

        //只能有一个P一个T，中间末尾和开头可以随便插入A。
        //但是必须满足开头的A的个数 * 中间的A的个数 = 结尾的A的个数，
        //而且P和T之间不能没有A～

        for (int i = 0; i < s.size(); i++)
        {
            //cout << s[i] << endl;

            if (s[i] != 'P' && s[i] != 'A' && s[i] != 'T') 
            {
                ans = false;
            }   

        }

        int p = count(s.begin(), s.end(), 'P');
        int a = count(s.begin(), s.end(), 'A');
        int t = count(s.begin(), s.end(), 'T');

        int pa = s.find("PA");
        int at = s.find("AT");

        if (p != 1 || t != 1 || a == 0 || pa == -1 || at == -1) 
        {
            ans = false;
        }

        if (ans == true)
        {
            int pp = s.find('P');
            int tt = s.find('T');

            int zuoa=0, mida=0, youa=0;

            for (int i = 0; i < pp; i ++ )
            {
                if (s[i] == 'A') zuoa ++;
            }

            for (int i = pp; i != tt; i ++ )
            {
                if (s[i] == 'A') mida ++;
            }

            for (int i =tt; i < s.size(); i ++ )
            {
                if (s[i] == 'A') youa ++;
            }

            if (zuoa * mida != youa) ans = false;
        }


        if (ans == true) cout << "YES";
        if (ans == false) cout << "NO";

        if (n != 0) cout << endl;

    }

    return 0;
}

题目描述

读入一个正整数 n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：
每个测试输入包含 1 个测试用例，即给出自然数 n 的值。这里保证 n 小于 10^100。

输出格式：
在一行内输出 n 的各位数字之和的每一位，拼音数字间有 1 空格，但一行中最后一个拼音数字后没有空格。

样例

输入样例：
1234567890987654321123456789
输出样例：
yi san wu

算法1

模拟

按需转换string和int即可，注意输出格式。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 10e6+10;

string s;

int main()
{
    cin >> s;

    int sum = 0;
    for (int i = 0; i < s.size(); i ++ )
    {
        sum += (s[i]-'0');
    }

    string str[10] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};

    string ans = to_string(sum);
    int l = ans.size();

    for (int i = 0; i < l; i ++ )
    {
        cout << str[(ans[i] - '0')];
        if (i != l-1) cout << ' ';
    }

    cout << endl;

    return 0;
}

题目描述

一个数组A中存有N（N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0 A1……AN-1）变换为（AN-M …… AN-1 A0 A1……AN-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动
的方法？

输入格式

每个输入包含一个测试用例，第1行输入N ( 1<=N<=100)、M（M>=0）；第2行输入N个整数，之间用空格分隔。

输出格式

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

样例

输入样例:
6 2
1 2 3 4 5 6
输出样例:
5 6 1 2 3 4

算法1

从输出做文章

如果m大于n，那么循环右移m位相当于循环右移m%n位，因为那些n倍的移动是多余的,
所以在使用m之前，先将m = m%n

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int a[110];

int main()
{
    int n,m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    if (m > n) m = m % n;


    for (int i = n-m+1; i <= n; i ++ ) cout << a[i] << ' ';
    for (int i =1; i <= n-m; i ++ ) 
    {
        if (i<n-m) cout << a[i] << ' ';
        else cout << a[i] << endl;
    }

    return 0;
}

题目描述

让我们用字母 B 来表示“百”、字母 S 表示“十”，用 12…n 来表示不为零的个位数字 n（<10），换个格式来输出任一个不超过 3 位的正整数。例如 234 应该被输出为 BBSSS1234，因为它有 2 个“百”、3 个“十”、以及个位的 4。

输入格式：
每个测试输入包含 1 个测试用例，给出正整数 n（<1000）。

输出格式：
每个测试用例的输出占一行，用规定的格式输出 n。

样例

输入样例 1：
234
输出样例 1：
BBSSS1234

算法1

模拟

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    //获取百位并输出
    int bai = n/100;
    n = n%100;
    while (bai--) cout << 'B';

    //获取十位并输出
    int shi = n/10;
    n = n%10;
    while (shi--) cout << 'S';

    //按格式输出个位
    for (int i = 1; i <= n; i ++ ) cout << i; 
    puts("");

    return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>

using namespace std;

const int N = 510;
int n;
int w[N][N], f[N][N];

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            cin >> w[i][j];


    for (int i = 1; i <= n; i ++ ) f[n][i] = w[n][i];

    for (int i = n - 1; i ; i -- )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i+1][j] + w[i][j], f[i+1][j+1] + w[i][j]);



    cout << f[1][1] << endl;

    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);

    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }

    while (m -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~