Codeforces847E题解

发表于 更新于

二分 + 贪心

题意翻译

输入n, 接着给你一个长度为n的字符串。 *代表包装, P代表人, .代表为空, 人移动一单位距离需要花费一秒，人可以向左或者向右移动。人只要走到包装的位置，就会把包装吃掉，问你最少需要多少秒。所有的包装就被人全吃完

Inputs and Outputs examples

Inputs’ e.g. #1

1
2
7
*..P*P*

Outputs e.g. #1

1
3

Inputs e.g. #2

1
2
10
.**PP.*P.*

Outputs e.g. #2

1
2

分析

ZR的mjy老师姐姐(姐姐敲可爱呢qwq)讲二分时候的例题.

我们考虑二分答案,二分人到达食物的最小时间$mid$,设人和食物的目标距离为$dis$,那么在遍历中可能有以下三种情况:

  1. 如果这个人前面的食物都已经被吃完,那么贪心往前遍历$mid$格

  2. 之前有没有被吃的食物,如果左边的食物距离较短,即$x > 3 \times dis$,那么先向左到达该目标,再向右移动

  3. 之前有没有被吃的食物,如果右边的食物距离较短,即$x \leq 3 \times dis$,那么先向右尽量走$i+\frac {x-mid}{2}$格,再向左到达该目标

后两种情况可以画图理解一下,具体细节可以康康代码

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// luogu-judger-enable-o2
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e5 + 10;
int n;
char payphone_X[MAXN];
/* functions */
namespace Solution{ // namespace for Solution
    inline bool check(int limit){ // check for binary_search.
        int unfindst = 0, havbefind = 0;
        FOR(i,1,n,1){
            if(payphone_X[i] == '*' && i > havbefind && !unfindst) unfindst = i;
            if(payphone_X[i] == 'P'){
                if(unfindst == 0) havbefind = i + limit;
                else {
                    int dis = i - unfindst;
                    if(dis > limit) return false;
                    //if the person who are standing on the place which dosen't have any food before it and the person walk for 'limit' steps,
                    // and he cannot find any food, we should return false,because that's means that 'limit' is too small.
                    else{
                        if(limit > (dis * 3)) havbefind = i + limit - dis * 2;
                        else havbefind = i + (limit - dis) / 2;
                        unfindst = 0;
                    }
                    if(havbefind >= n) return true;
                }
            }
        }
        if(unfindst) return 0;
        return 1;
    }
    inline int binary_solve(int l,int r){
        int ans = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(check(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        return ans;
    }
}
int main(int argc,char *argv[]){
    scanf("%d",&n);
    scanf("%s",payphone_X+1);
    int l = 0,r = (n << 1);
    printf("%d\n",Solution::binary_solve(l,r));
    return 0;
}

THE END