CodeForces 651D – Watchmen [二分]

Link

传送门

Problem

Vasya’s telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last photo you reach photo 1. It takes a seconds to swipe from photo to adjacent.

For each photo it is known which orientation is intended for it — horizontal or vertical. Phone is in the vertical orientation and can’t be rotated. It takes b second to change orientation of the photo.

Vasya has T seconds to watch photos. He want to watch as many photos as possible. If Vasya opens the photo for the first time, he spends 1 second to notice all details in it. If photo is in the wrong orientation, he spends b seconds on rotating it before watching it. If Vasya has already opened the photo, he just skips it (so he doesn’t spend any time for watching it or for changing its orientation). It is not allowed to skip unseen photos.

Help Vasya find the maximum number of photos he is able to watch during T seconds.

Mean

一部手机中有N张图片,每看一张图片需要一秒,滑动到下一张需要A秒,手机是固定竖直放置的,如果照片方向不对需要B秒转动图片。你可以从第1张往右滑到第2张,也可以往左滑到第N张。以前看过的图片不需要时间看和旋转。问你在T秒内最多能看多少张图片。

Analysis

首先明确图片从最右边滑到最左边(或者从最左边滑到最右边)的次数最多只有一次,那么可以二分答案,枚举能滑动到的最右边,判断能否在T秒内完成即可。

比赛完根据官方题解和网上的题解做的。然而还是因为写错了一个变量改了一晚上…

加强独立思考能力,最近几个月比赛比较多,要加油了。积极思考….

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 512000;
ll N, A, B, T;
ll s[maxn];
char str[maxn];

bool judge(ll sum) {
    for(ll i = 1; i <= sum; ++i) {
        ll t1 = s[i] + (s[N] - s[N - (sum - i)]);
        ll t2 = min(i - 1 + sum - 1, sum - i + sum - 1) * A;
        if(t1 + t2 + sum <= T)
            return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> A >> B >> T >> str + 1;
    for(int i = 1; i <= N; ++i)
        s[i] = s[i-1] + B * (str[i] == 'w');
    ll L = 0, R = N, ok = 0;
    while(L <= R) {
        ll mid = L + (R - L) / 2;
        if(judge(mid)) {
            ok = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    cout << ok << endl;
    return 0;
}

欢迎留言