程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NOJ1553---Beautiful Walls(尺取法)

NOJ1553---Beautiful Walls(尺取法)

編輯：C++入門知識

NOJ1553---Beautiful Walls(尺取法)

問題描述
To simplify the building process, XadillaX built some template on the ground. The template is a very big wall and the height of each unit may be different.

8Mao and Hungar have to choose any part of this wall as their own wall.

The part(i, j) means the wall between unit(i) and unit(j) with their heights.
What Hungar thinks a beautiful wall is that the height of each unit is unique.
Now give you a wall-template, you should tell Hungar that how many ways he can choose to copy his own wall?
輸入
This problem contains several cases, ends with EOF.
The first line of each case is one integer N (0 ＜ N ≤ 100000) which indicates the side length (number of units) of the wall-template.
The second line contains N integers which indicate the height of each unit. (0 < height <= 100000)
輸出
For each case, you should output the number of ways that Hungar can choose.
樣例輸入

5
3 4 5 5 2
3
1 2 3

樣例輸出

9
6

提示

無

來源

cjl

操作

Wine93出的一道題我是用尺取做的,只要記錄每個數上一次出現的位置就行了

/*************************************************************************
    > File Name: NOJ1553.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2015年04月16日 星期四 19時36分28秒
 ************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair  PLL;

static const int N = 100100;
int height[N];
int last[N];
int _hash[N];

int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        memset(last, -1, sizeof(last));
        memset(_hash, -1, sizeof(_hash));
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &height[i]);
            int x = _hash[height[i]];
            last[i] = x;
            _hash[height[i]] = i;
        }
        LL ans = 0;
        int l = 1, r = 1, len = 0;
        while (1)
        {
            while (r <= n && last[r] < l)
            {
                ++len;
                ++r;
            }
            ans += len;
            --len;
            ++l;
            if (l > r)
            {
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}