01/10/2018, 00:21

Gặp rắc rối với bài "Circular Array Rotation" trên Hackerrank

Em vừa gặp cái bài như hình dưới, nhưng khi giải thì bị lỗi time out @@ nhờ mấy bác cho em 1 giải pháp tối ưu hơn ạ , em cảm ơn

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;


int main(){
    int n;
    int k;
    int q;
    int temp;
    cin >> n >> k >> q;
    vector<int> a(n);
    
    for(int a_i = 0;a_i < n;a_i++){
       cin >> a[a_i];
    }

    for ( int i = 0 ; i <k ; i++)
    {
         temp = a[n-1];
        for ( int j = n-1 ; j >= 0 ; j--)
           {
               if ( j == 0)
               {
                    a[j] = temp;
               }
               else
               {
                    a[j] = a[j-1];
                }
     
            }
        
    }
    
    
    for(int a0 = 0; a0 < q; a0++){
        int m;
        cin >> m;
        cout<<a[m]<<endl;
    }
    
    
    
    return 0;
}

And

Nguyễn Xuân Phúc viết 02:26 ngày 01/10/2018

Nhận xét:

Sau 1 lần xoay, phần tử thứ i sẽ trở thành phần tử thứ (i+1)%n (với n là kích thước mảng, và chỉ số bắt đầu từ 0)
Từ nhận xét 1 -> khi xoay thêm 1 lần nữa (sau 2 lần xoay), thì phần tử thứ (i+1)%n tiếp tục thành ((i+1)%n + 1)%n, hay có thể phân tích thành (i + 2) % n.
Như vậy, sau k bước thì phần tử thứ i sẽ trở thành phần tử thứ (i + k) % n
Từ đó ta có 20đ.
Btw: linux thì dùng ibus unikey để mà ghi tiếng Việt!

Nguyễn Hoàng Trung viết 02:36 ngày 01/10/2018

Em quên :v Bác có thể giải thích giùm em công thức này được không @@ [quote=“nxphuc, post:2, topic:36405”]
Sau 1 lần xoay, phần tử thứ i sẽ trở thành phần tử thứ (i+1)%n (với n là kích thước mảng, và chỉ số bắt đầu từ 0)
[/quote]

Nguyễn Xuân Phúc viết 02:28 ngày 01/10/2018

ủa thì trong cái đề bài ra chứ có gì cao siêu đâu???

Nguyễn Hoàng Trung viết 02:24 ngày 01/10/2018

Ý em là làm sao bác biết được phần tử i sẽ trở thành phần tử thứ ( i +1 ) %n ấy, em đang thắc mắc làm sao bác thành lập được công thức này

Nguyễn Xuân Phúc viết 02:27 ngày 01/10/2018

nhìn trong đề bài? có phải là