PAT 1044

题目 ： Shopping in Mars

分值 ： 25
难度 ： 中等题
思路 ： 二分搜索以及数组优化，data[i] 存放 i 以前的所有值加和
坑点 ： 用了二分和数组优化
评语 ： 二分细节问题还是有，对二分不是得心应手。

具体代码如下

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
51
#include <iostream>
#include <vector>
using namespace std;
vector<int> db ;
vector<string> ans;
int min_ = 99999999 ;
int binary_Search(int base , int s , int e ,int target)
{
    if(s >= e ) return s ;
    int ss =s , ee =e ;
    while(ss < ee )
    {
        int mid = (ss+ee)/2 ;
        if(db[mid]-db[base] ==target ) return mid;
        else if(db[mid] - db[base] < target) ss = mid+1 ;
        else ee = mid ;
    }
    return ss ;
}
int main()
{
    int N , K ,t ,sum = 0;
    cin >> N >> K ;
    db.resize(N+1);
    db[0] = 0 ;
    for(int i = 1 ; i<= N ; i++)
    {
        cin >> t ;
        sum +=t ;
        db[i] = sum ;
    }
    for(int i = 0 ; i< N  ; i++) // 1-1 = db[1] - db[0]    n-n = db[n] - db[n-1]
    {
        int mid = binary_Search(i , i , N ,K);
        int k = min_ ;
        if(db[mid] - db[i] -K == min_)
        {
            string s = to_string(i+1) +"-"+to_string(mid) ;
            ans.push_back(s) ;
        }
        else if(db[mid]-db[i] >=K && db[mid] -db[i] - K < min_)
        {
            ans.clear();
            min_= db[mid] - db[i] - K ;
            string s = to_string(i+1) +"-"+to_string(mid) ;
            ans.push_back(s) ;
        }
    }
    for(int i = 0 ; i < ans.size() ;i++)
        cout << ans[i] <<endl ;
}