C11PAIRS – spoj

Đề bài

Thuật toán

-Đầu tiên ta khởi tạo một stack để lưu chiều cao của các bạn theo thứ tự không tăng (s[i]<=s[i-1])

-Đầu tiên ta cho a[n] vào stack, khởi tạo ds=0,sn=1(sn là số phần tử trong ngăn xếp);

-Duyệt i từ n-1 về 1, với mỗi i:

+Tìm vị trí cuối cùng trong stacks mà s[i]>a[i], giả sử ta gọi là vt.

+Nếu vt=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy mọi người trong stack vì vậy ds+=sn;

+Nếu vt!=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy từ người thứ vt đến người thứ sn trong stack vì vậy ds+=(sn-vt+1);

+Tiếp theo ta sẽ bỏ các s[i]<a[i] trong stack sau đó thêm a[i] vào stack.

-Kết quả của bài này chính là ds.

-Từ đó ta thu được thuật toán với đpt O(n*log(n)), mặc dù có thể giảm đpt xuống còn O(n) nhưng mình thấy thuật toán này khá đơn giản và dễ code, có thể là ngắn hơn. Đây là code của mình:

Code

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;
 
int n, i, j, a[MAXN], c[MAXN], s[MAXN], top, tmp;
ll ans;
 
int main() {
        ios_base::sync_with_stdio(0); cin.tie(0);
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif //yeulaptrinh.pw
    cin >> n;
    FOR(i,1,n) cin >> a[i];
 
    top = 0;
    FOR(i,1,n) {
        tmp = 1;
        while (top&&s[top]<=a[i]) {
            ans += c[top];
            if (s[top]==a[i]) tmp += c[top];
            c[top] = 0; top--;
        }
        if (top) ans++;
        // push
        top++;
        s[top] = a[i];
        c[top] = tmp;
    }
    cout << ans;
	return 0;
}
Khuyên dùng

 

Speak Your Mind

*