Giải bài ntucoder DATA - Dãy tăng

Link bài:

Thuật toán:

• Với bài này ta chỉ cần duyệt O (n).
  
• Xét từng phần tử thỏa mãn dãy tăng dần. Nếu gặp phần tử i ≤ phần tử i-1, ta sẽ xét dãy i→n xem liệu đây có là dãy tăng hay không.
  
• Điều kiện ràng buộc rằng phần tử thứ n phải nhỏ hơn phần tử thứ nhất, nếu không thì trong bất cứ trường hợp nào cũng không có kết quả.

Code:

Mã:

#include <bits/stdc++.h>
using namespace std;

int n, preans;
int a[100007];

bool check(int i){
    for (int j = i+1; j <= n; j++)
        if (a[j] <= a[j-1]) return false;
    if (a[n] >= a[1]) return false;
    return true;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("data.inp", "r", stdin);
    //freopen("data.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a;
    for (int i = 1; i <= n; i++)
        if (a == a[i-1]) {preans = 0; break;} else
        if (a < a[i-1] && check(i)) {cout << i; preans = i; break;} else
        if (a < a[i-1] && !check(i)) {cout << -1; preans = -1; break;}
    if (!preans) cout << -1;
    
    return 0;
}