周日gym补题

ACM

周日补题

I

分成若干个组，每个组差值最大为该组的花费，为总的花费最小

题解

二分答案+dp判断

code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 3e5+10;
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long int lli;
lli aa[MAXN];
int n,m;
int dp[MAXN];
bool check(lli x)
{
    memset(dp,0,sizeof(dp));  //dp[i]表示[1,i]能否被完整分成满足条件的几段
    dp[0]=1;
    int s=1;
    for(int i=1;i<=n;i++)
    {
        while(aa[i]-aa[s]>x) s++;
        while(i-s+1>=m)
        {
            if(dp[s-1])
            {
                dp[i]=1;
                break;
            }
            s++;
        }
    }
    return dp[n];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&aa[i]);
    }
    aa[0]=INF;
    sort(aa+1,aa+1+n);
    lli l=0;
    lli r=aa[n]-aa[1];
    if(m==1)
    {
        printf("0\n");
        return 0;
    }
    while(l<r)
    {
        lli mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",r);
    return 0;
}

K

题解

  1. 对于第一段，它的区间应该是[ x[1] = s[1] , y[1] = s[1]+g[1] ]
  2. 对于第i段，它的区间应该是[ x[i] = max( x[i-1]-1, s[i] ) , y[i] = min( y[i-1]+1, s[i] + g[i] )]
  3. 若存在某点使得x大于y，则说明区间不存在，直接输出-1
  4. 从尾部重复1，2的步骤，那么最后得到的区间一定是可行区域，y[i]对应的值就是道路能修的最宽值。

扫描两遍的思想很重要！！！

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
ll r[maxn], g[maxn];
ll mini[maxn], maxi[maxn];
int n;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>r[i]>>g[i];
    }
    mini[0] = r[0], maxi[0] = r[0]+g[0];
    for(int i=1; i<n; i++){
        mini[i] = max(mini[i-1]-1, r[i]);//这里一开始写错了。。。
        maxi[i] = min(maxi[i-1]+1, r[i]+g[i]);
        if(mini[i]>maxi[i]){
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=n-2; i>=0; i--){
        mini[i] = max(mini[i+1]-1, mini[i]);
        maxi[i] = min(maxi[i+1]+1, maxi[i]);
        if(mini[i]>maxi[i]){
            cout<<-1<<endl;
            return 0;
        }
    }
    ll ans = 0;
    for(int i=0; i<n; i++){
        ans += (maxi[i]-r[i]);
    }
    cout<<ans<<endl;
    for(int i=0; i<n; i++){
        cout<<maxi[i]<<" ";
    }
    cout<<endl;
    return 0;
}

未解决的问题

本文标题:周日gym补题

文章作者:Babydragon

发布时间:2018-06-10, 17:42:44

最后更新:2018-06-12, 14:31:11

原始链接:http://baolintian.github.io/2018/06/10/周日gym补题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. I
    1. 1.1. 题解
    2. 1.2. code
  2. 2. K
    1. 2.1. 题解
    2. 2.2. ac code
  3. 3. 未解决的问题
{{ live2d() }}