HrbustOJ 2063 萌萌哒十五酱的情书~

发表于 | 分类于 | 阅读次数: |
字数统计: 617 | 阅读时长 ≈ 2

萌萌哒十五酱的情书~

Time Limit: 150 MS Memory Limit: 1515 K

Total Submit: 86(32 users) Total Accepted: 21(18 users) Rating: Special Judge: No

Description

因为十五酱实在是太萌了所以她经常会收到爱慕者的情书！！！！！！！！！！~

当然因为情书太多了所以她没有时间都读完

于是她把给她的情书从左到右划分成n个区域，在每个区域的边界依次表上0~n，然后她将经行m次操作，每次她都会选择一个数字ai，把纸带沿这个数字当前所在的位置翻折（假如已经在边界上了那就相当于什么都不做啦~）。

十五想知道经过m次对折之后她还需要读多长的情书。

Input

多组数据

第一行为两个正整数n（1<=n<=10^18），m（m<=3000），表示纸带的长度和操作的次数。

接下来的一行为m个整数ai（1<=ai<=n），其中ai表示第i次选择的数字。

Output

多组数据输出

输出文件中每组数据输出一行为一个整数，即纸带最后的长度。

Sample Input

5
0 2
0 4
1 3
1 2
1 5

Sample Output

3

Hint

十五酱最萌了昂~

Source

HCPC2014校赛训练赛 6

题解

由样例，0的时候是衬衫，找属性值最接近的裤子，比如 0 2 找到 1 3，属性差值的绝对值是1，而 0 4 也找到 1 3 ，属性差值的绝对值也是1，此时应该选取属性值较小的衣服，是 0 2 这一组，并扔进衣柜(清除)，所以可以用 multiset 多重映射容器做这个题，里面有 lower_bound() 二分查找算法返回不小于某个值的一个指针，正好可以用来解决这个题。
代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <set>
#include <cmath>

using namespace std ;

const int MOD = 1e6 ;

int main(){
    int t ;
    while ( cin >> t ){
        int close_kind , close_val ;
        int index ;
        int ans = 0 ;
        multiset<int> mul ;
        for ( int i = 0 ; i < t ; i ++ ){
            cin >> close_kind >> close_val ;
            if ( mul.empty() ){
                index = close_kind ;
            }
            if ( mul.empty() || index == close_kind ){
                mul.insert(close_val) ;
                continue ;
            }
            multiset<int>::iterator it_left , it_right = mul.begin() ;
            it_right = mul.lower_bound(close_val) ;
            if ( it_right == mul.end() ){
                it_right -- ;
                ans += (close_val - *it_right) % MOD ;
                mul.erase(it_right) ;
            }else if ( it_right == mul.begin() ){
                ans += (*it_right - close_val) % MOD ;
                mul.erase(it_right) ;
            }else{
                it_left = it_right ;
                it_left -- ;
                if ( close_val - *it_left <= *it_right - close_val ){
                    ans += (close_val - *it_left) % MOD ;
                    mul.erase(it_left) ;
                }else{
                    ans += (*it_right - close_val) % MOD ;
                    mul.erase(it_right) ;
                }
            }
            ans %= MOD ;
        }
        cout << ans << endl ;
    }
    return 0 ;
}