In hướng di chuyển giữ trong khoảng [-k, +k] C++

Cho giới hạn K và mảng bước nhảy. Xác định hướng (+/-) cho mỗi bước sao cho vị trí luôn trong [-K, K]. Ưu tiên dương: nếu + bước không vượt K thì đi dương, else nếu - bước không vượt -K thì đi âm, else thất bại.

Tham lam ưu tiên dương

Vị trí pos=0. Duyệt mảng: nếu pos+a[i] trong [-K,K] → POSITIVE, pos+=a[i]. Ngược lại nếu pos-a[i] trong [-K,K] → NEGATIVE, pos-=a[i]. Ngược lại → -1.

Ví dụ minh họa

#include <iostream>
using namespace std;

void printDirections(int a[], int n, int k) {
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (pos + a[i] <= k && pos + a[i] >= -k) {
            pos += a[i];
            cout << "POSITIVE\t";
        } else if (pos - a[i] >= -k && pos - a[i] <= k) {
            pos -= a[i];
            cout << "NEGATIVE\t";
        } else {
            cout << -1;
            return;
        }
    }
}

int main() {
    int a[] = {12, 24, 9, 17, 8};
    int n = sizeof(a)/sizeof(a[0]);
    int k = 40;
    printDirections(a, n, k);
    return 0;
}

Kết quả

POSITIVE    POSITIVE    NEGATIVE    NEGATIVE    POSITIVE