SPOJ：GENERAL（超过时间限制） [英] SPOJ: GENERAL (Time limit exceeded)

问题描述

我一直在努力解决这个简单的问题（ http://br.spoj.com/problems / GENERAL / ）在spoj相当一段时间了，但我继续得到TLE（超过时间限制）由于某种原因。

I have been trying to solve this simple problem (http://br.spoj.com/problems/GENERAL/) on spoj for quite some time now, but I keep on getting TLE (Time limit exceeded) for some reason.

由于问题是葡萄牙语，问题的简单描述是这样的（没有故事）：

Since the problem is in Portuguese, a brief description of the problem is like this (without the story):

你得到一个大小为 N的数组，你必须以
的升序排列数组，这样一个元素只能与$ b交换$ b元素，距离它 k 。如果数组可以是
sorted，那么如果不能排序打印 impossivel ，那么打印要以
升序排列所需的交换数量。

You are given an array of size N, you have to arrange the array in ascending order, such that an element can only be swapped with elements which are at a distance k from it. If the array can be sorted then print the number of swaps required to arrange them in ascending order, if it cannot be sorted print impossivel.

这是我的代码::

#include <iostream>
#include <cstdio>

using namespace std;
int a[100005];
int main() {
    int t;
    int n, k;
    scanf("%d", &t); //number of test cases
    while(t--) {
        scanf("%d %d", &n, &k);
        bool result = true;
        int count = 0;

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

        for(int i = n; i > 0; i = i - k) {
            int j = 0;
            for( ; j < i - k; j++) {
                if(a[j] > a[j + k]) {
                    int temp = a[j];
                    a[j] = a[j + k];
                    a[j + k] = temp;
                    count++;
                }
            }

            for( ; j < i - 1; j++) {
                if(a[j] > a[j + 1]) {
                    result = false;
                    break;
                }
            }

            if(!result)
                break;
        }
        if(result)
            printf("%d\n", count);
        else
            printf("impossivel\n");
    }
}

我的逻辑：我执行 N / k 。我将循环变量 i初始化为 N 。在每次迭代中，我使用距离 k 的元素检查 ik 元素，如果它们要交换，则交换它们并增加所需的交换次数，否则我什么都不做。然后，我检查从 ik 到 i 的元素，如果他们是升序，如果不是我打破循环和打印impossivel，否则我改变 i 更改为 ik ，然后再次执行循环。根据我的逻辑，每次迭代后，最后的 k 元素将按升序排列，如果可以对它们进行排序，因为在每一步我都将更大的元素移动到右边。

My logic : I perform N/k iterations on the array. I initialize the loop variable i to N. In each iteration I check i-k elements with the element at a distance k from it, if they are to be swapped then I swap them and increment the number of swaps needed, else I do nothing. Then I check the elements from i-k to i, if they are in ascending order, if not I break the loop and print "impossivel", else I change i to i-k and again perform the loop. By my logic after every iteration the last k elements will be in ascending order, if is possible to sort them, since at every step I move the elements which are greater to the right.

这对你似乎是正确的吗？如何进一步优化呢？感谢您提供任何帮助。 ：）

Does this seem correct to you? How can optimize this further? Thanks for any help in advance. :)

推荐答案

每个都分成n / k个元素的k个子列表。

Separate into k sublists of n/k elements each.

检查不可能条件。

不可能条件

让k = 2 ，

3 4 1 2是数组

3 4 1 2 is the array

对于n / k列表，维护数组，存在于O（1）中。

For n/k lists maintain array to see if a number is present in O(1).

例如。间隔为2

我们可以分为两个子列表，3 1和4 2
现在我们知道sorted是

We can divide into two sublists , 3 1 and 4 2 Now we know sorted is

1 2 3 4（使用计数排序作为1和n O（n）之间的高度）

1 2 3 4 (Use counting sort as heights between 1 and n O(n))

因此，我们期望1。现在问，可以来这里吗？ [Y]

So , we expect 1 at first place. Now ask , can 1 come here? If only it is in sublist.[Y]

如果[N]说不可能

k次合并排序，k * n / k（log（n / k））

k times Merge sort, k * n/k(log(n/k))

（反转次数等于对数组进行排序的最小相邻交换数[已知属性]
引用：
通过使用最小交换来交换相邻元素来排序序列
）

(The number of inversions is equal to the minimum number of adjacent swaps to sort an array [known property] refer: Sorting a sequence by swapping adjacent elements using minimum swaps )

方法的复杂度为n log n，这很容易通过：）

complexity of approach is n log n , which will easily pass :)

这篇关于SPOJ：GENERAL（超过时间限制）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！