[TJOI2007]路标设置 题解

题目链接：https://www.luogu.com.cn/problem/P3853

题目大意：给出一个递增数组，插入K个值，使其差分数列的最大值最小；值得注意的是，此题中每个数字都是整数

考点：整数二分

错误思路：利用堆排，取最大值直接二分

code：

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int l , n , k;
 6 //int a[1000010];
 7 priority_queue < int > a;
 8 
 9 signed main()
10 {
11     cin >> l >> n >> k;
12     int l , r;cin >> l;
13     for(int i = 1;i < n;i ++)
14     {
15         cin >> r;
16         a.push( r - l );
17         r = l;
18     }
19     int tmp;bool tag;
20     while( k -- )
21     {
22         tmp = a.top();
23         a.pop();
24         tag = 0;
25         if( tmp % 2 ) tag ++;
26         tmp /= 2;
27         if( tag ) tmp ++;
28         a.push( tmp );
29     }
30     cout << a.top() << endl;
31 //    for(int i = 1;i < n;i ++)
32 //    {
33 //        cout << a[i] << " ";
34 //    }
35     
36 }

hack：有的区段三分即可

正解：二分寻找答案

 code：

再普通不过的二分：

int ef( int l , int r )
{
    if( l == r ) return l;
    int mid = ( l + r ) / 2;
    if( chck( mid ) )  return ef( l , mid );
    else return ef( mid + 1 , r );
}

检查函数：

bool chck( int len )
{
    int pn = K;//分割的剩余次数 
    for(int i = 2;i <= N;i ++)
    {
        int prt = a[i] - a[i-1];
        if( prt <= len ) continue;
        pn -= ( prt / len );
        if( prt % len ) pn --;
        pn ++;
        if( pn < 0 ) return 0;
    }
    return 1;
}

主函数部分：

signed main()
{
    cin >> L >> N >> K;
    for(int i = 1;i <= N;i ++) cin >> a[i];
    cout << ef( 0 , L ) << endl;
    return 0;    
} 

值得注意的是，遇到初始分个节点为 (0,2) 之类的情况，则无法二分，需要进行特判

if( l == 0 && r == 2 ) return ( l + 1 );

AC代码：

 1 #include <bits/stdc++.h>
 2 #define int long long
 3 
 4 using namespace std;
 5 
 6 int L , N , K;
 7 int a[1000010];
 8 
 9 bool chck( int len )
10 {
11 //    if( len == 0 )
12 //    {
13 //        return 1;
14 //    }
15     int pn = K;//分割的剩余次数 
16     for(int i = 2;i <= N;i ++)
17     {
18         int prt = a[i] - a[i-1];
19         if( prt <= len ) continue;
20         pn -= ( prt / len );
21         if( prt % len ) pn --;
22         pn ++;
23 //        cout << "pn= " << pn << endl;
24         if( pn < 0 ) return 0;
25     }
26     return 1;
27 }
28 
29 int ef( int l , int r )
30 {
31 //    cout << "l,r: " << l << " " << r << endl;
32     
33     if( l == r ) return l;
34     if( l == 0 && r == 2 ) return ( l + 1 );
35     
36     
37     int mid = ( l + r ) / 2;
38     
39     
40 //    cout << "mid: " << mid << endl;
41     
42     if( chck( mid ) ) //可以用 
43     {
44 //        cout << "状态： " << 1 << endl; 
45         return ef( l , mid );
46     }
47     else 
48     {
49 //        cout << "状态： " << 0 << endl; 
50         return ef( mid + 1 , r );
51     }
52 }
53 
54 signed main()
55 {
56     cin >> L >> N >> K;
57     a[0] = 0;
58     for(int i = 1;i <= N;i ++)
59     {
60         cin >> a[i];
61     }
62     a[N+1] = L;
63      
64     cout << ef( 0 , L ) << endl;
65     
66     return 0;    
67 } 
68 /*
69 
70 101 2 1
71 0 101
72 
73 2 2 1
74 0 2
75 
76 */