原题链接

Acwing

思路

容易发现，当单调不增。直接二分即可。

一个需要注意的细节是，此处要求的是的最小值。由于二次函数的特殊性 ，实际上我们不需要直接考虑这样一个目标函数（单峰，直接求解需要使用三分法），我们只需要求出左侧距离其最近的一个点即可，而其右侧距离最小的点一定是所求点的下一个点。

另一个需要注意的细节是，为了快速求解区间和，需要预处理前缀和。

题外话-整数域二分的实现

说明

此处使用的是 lyd书中给出的实现方法，其主要特点为：

  1. 有两种不同的实现二分的形式（分别为求一个数字的后继以及求一个数字的前驱）；
  2. 二分结束时，若在界内，则一定是解；反之，说明无解。

具体实现

以下假定使用数组a[1-N]保存单调序列，并且我们使用满足条件来完成一定程度的抽象。我们假定，如果一个元素满足条件，那么其后继一定也满足条件。

如果是求一个元素的后继（在一个单调的序列中，满足条件的最小的一个元素）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* find the next value
 * return: -1 means no solution, otherwise the solution
 */
 
int solve(int* a, int arr_len, int val){
	int l, r;
    l = 1;
    r = arr_len; // arr_len will never be taken.If l ends at arr_len, there is no such value
    while(l<r){
        int mid = (l+r)>>1;
        if (satisify(a[mid])){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    if (l == arr_len){
		return -1;
    }
    return a[l];
}

对以上代码做一个简单的讲解。

line 8: 由于永远不会取值，故而将设置为一个越界值，如果发现停留在该值上，说明无解。

line 12: 由于希望找到满足性质的最小元素，并且当前元素满足性质，故而我们舍弃右半区间。

求一个元素的前驱是类似的，但是需要注意求$mid$时的计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* find the previous value
 * return: -1 means no solution, otherwise the solution
 */
 
int solve(int* a, int arr_len, int val){
	int l, r;
    l = 0; // 0  will never be taken.If l ends at 0, there is no such value
    r = arr_len-1; 
    while(l<r){
        int mid = (l+r+1)>>1;
        if (satisify(a[mid])){
            l = mid;
        }else{
            r = mid-1;
        }
    }
    if (l == 0){
		return -1;
    }
    return a[l];
}

实现

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
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2000000 + 10;
/* all starts form index 1 */
ll w[N];
ll v[N];
ll sum[N]; 
ll cnt[N];
pair<int, int> interval[N];

ll caculate_Y(int W,int arr_len, int interval_len){
    memset(sum, 0, sizeof(sum));
    memset(cnt, 0, sizeof(cnt));
    
    for(int i=1;i<=arr_len;i++){
        if(w[i]>=W){
            cnt[i]=1;
            sum[i] += v[i];
        }
        sum[i] += sum[i-1];
        cnt[i] += cnt[i-1];
    }
    
    ll ans=0;
    for(int i=1;i<=interval_len;i++){
        ll sum_of_yi = sum[interval[i].second]-sum[interval[i].first-1];
        ll sum_of_cnt = cnt[interval[i].second] - cnt[interval[i].first-1];
        ans += sum_of_yi * sum_of_cnt;
    }
    
    return ans;
}

int main(){
    ll arr_len, interval_len, S;
    cin>>arr_len>>interval_len>>S;
    
    for(int i=1;i<=arr_len;i++){
        cin>>w[i]>>v[i];
    }
    
    for(int i=1;i<=interval_len;i++){
        cin>>interval[i].first>>interval[i].second;
    }
    
    ll ans = LONG_LONG_MAX;
    
    int l=0,r =1000000+10, mid;
    while(l<r){
        mid = (l+r+1)>>1;
        ll res = caculate_Y(mid, arr_len, interval_len);
        if(res >= S)l = mid;
        else{
            r = mid-1;
        }
    }

    ans = min(ans, min(abs(caculate_Y(l, arr_len, interval_len)-S),abs(caculate_Y(l+1, arr_len, interval_len)-S)));
    cout<<ans<<endl;
    return 0;
}