Инверсии и перестановки

@Montanaa · Регистрация: 21.03.2011

Author24 — интернет-сервис помощи студентам

Ребят, помогите пожалуйста, сделать 2 задачки, буду очень вам признателен!
Заранее огромное спасибо.

1.Дана перестановка. Наименьшее число обменов, чтобы ее отсортировать.

Входные данные
Число N (1 <= N <= 10000), затем перестановка.

Выходные данные
Выведите ответ.

Пример

Ввод
5
1 4 3 5 2

Вывод
2

2.Школьник В*** записал на доске N чисел и утверждает, что это перестановка чисел 1, 2, ...,N, то есть эти и только эти числа, записанные в каком-то порядке. Прав ли он?

Входные данные
В первой строке входного файла записано натуральное число M (1 <= M <= 10) - количество тестов в файле. Далее следует M строк, каждая из которых описывает запись на доске в виде: N, A1, A2, ..., AN, где A1, A2, ..., AN (1 <= AK <= 1000, для всех K=1, ...,N) -- числа записанные на доске, а N (1 <= N <= 1000) -- их количество.

Выходные данные
Для каждого из M тестов выведите ответ в отдельную строку. Ответ "Yes" означает, что данная последовательность является перестановкой, а "No", что не является.

Пример

Ввод
3
4 1 3 2 2
4 4 1 3 2
4 1 2 3 3

Вывод
No
Yes
No

Пожалуйста, кому не трудно..

Добавлено через 12 минут
Сделайте хотя бы одну ребят, очень вас прошу!

Потратьте немного своего времени, пожалуйста.. (

valeriikozlov · 25.10.2011, 18:24

1-ая:

C

#include <stdio.h>
 
int main()
{ 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);  
    int N, mas[1000], i, tmp, col=0;
    scanf("%d", &N);
    for(i=0; i<N; i++)
        scanf("%d", &mas[i]);
    for(i=0; i<N; i++)
        while(mas[i]!=i+1)
        {
            tmp=mas[i];
            mas[i]=mas[tmp-1];
            mas[tmp-1]=tmp;
            col++;
        }
    printf("%d", col);
        return 0;
}

@diagon · 25.10.2011, 18:34

2 - проверьте

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    int m;
    
    std::cin >> m;
    while ( m-- )
    {
        int n;
        std::cin >> n;
        std::vector<int> arr(n);
        
        for (int i = 0; i < n; ++i)
            std::cin >> arr[i];
        
        std::vector<int> tmp(n);
        for (int i = 0; i < n; ++i)
            tmp[i] = i + 1;
        
        std::sort( arr.begin(), arr.end() );
        
        std::cout << ( arr == tmp ? "Yes" : "No" );
    }
    
}

Если мешает то, что ответ выводиться во время ввода:

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
int main()
{
    int m;
    std::queue< std::string > answer;
    
    std::cin >> m;
    while ( m-- )
    {
        int n;
        std::cin >> n;
        std::vector<int> arr(n);
        
        for (int i = 0; i < n; ++i)
            std::cin >> arr[i];
        
        std::vector<int> tmp(n);
        for (int i = 0; i < n; ++i)
            tmp[i] = i + 1;
        
        std::sort( arr.begin(), arr.end() );
        
        answer.push( arr == tmp ? "Yes" : "No" );
    }
    
    while( !answer.empty() )
    {
        std::cout << answer.front() << std::endl;
        answer.pop();
    }
    
}

@Montanaa · 25.10.2011, 20:11 **[ТС]**

Сообщение от diagon

2 - проверьте

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    int m;
    
    std::cin >> m;
    while ( m-- )
    {
        int n;
        std::cin >> n;
        std::vector<int> arr(n);
        
        for (int i = 0; i < n; ++i)
            std::cin >> arr[i];
        
        std::vector<int> tmp(n);
        for (int i = 0; i < n; ++i)
            tmp[i] = i + 1;
        
        std::sort( arr.begin(), arr.end() );
        
        std::cout << ( arr == tmp ? "Yes" : "No" );
    }
    
}

Если мешает то, что ответ выводиться во время ввода:

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
int main()
{
    int m;
    std::queue< std::string > answer;
    
    std::cin >> m;
    while ( m-- )
    {
        int n;
        std::cin >> n;
        std::vector<int> arr(n);
        
        for (int i = 0; i < n; ++i)
            std::cin >> arr[i];
        
        std::vector<int> tmp(n);
        for (int i = 0; i < n; ++i)
            tmp[i] = i + 1;
        
        std::sort( arr.begin(), arr.end() );
        
        answer.push( arr == tmp ? "Yes" : "No" );
    }
    
    while( !answer.empty() )
    {
        std::cout << answer.front() << std::endl;
        answer.pop();
    }
    
}

второй вариант не работает (

Добавлено через 1 час 16 минут
пишет ошибку в:

C++

1	std::cout << answer.front() << std::endl;

@Montanaa 5 / 5 / 2 Регистрация: 21.03.2011 Сообщений: 79
		1
	Инверсии и перестановки 25.10.2011, 18:09. Показов 4986. Ответов 3 Метки нет (Все метки) Ребят, помогите пожалуйста, сделать 2 задачки, буду очень вам признателен! Заранее огромное спасибо. 1.Дана перестановка. Наименьшее число обменов, чтобы ее отсортировать. Входные данные Число N (1 <= N <= 10000), затем перестановка. Выходные данные Выведите ответ. Пример Ввод 5 1 4 3 5 2 Вывод 2 2.Школьник В*** записал на доске N чисел и утверждает, что это перестановка чисел 1, 2, ...,N, то есть эти и только эти числа, записанные в каком-то порядке. Прав ли он? Входные данные В первой строке входного файла записано натуральное число M (1 <= M <= 10) - количество тестов в файле. Далее следует M строк, каждая из которых описывает запись на доске в виде: N, A1, A2, ..., AN, где A1, A2, ..., AN (1 <= AK <= 1000, для всех K=1, ...,N) -- числа записанные на доске, а N (1 <= N <= 1000) -- их количество. Выходные данные Для каждого из M тестов выведите ответ в отдельную строку. Ответ "Yes" означает, что данная последовательность является перестановкой, а "No", что не является. Пример Ввод 3 4 1 3 2 2 4 4 1 3 2 4 1 2 3 3 Вывод No Yes No Пожалуйста, кому не трудно.. Добавлено через 12 минут Сделайте хотя бы одну ребят, очень вас прошу! Потратьте немного своего времени, пожалуйста.. ( 0

	25.10.2011, 20:11

Опции темы