Codeforces Round #345 (Div. 1) B Image Preview

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

B. Image Preview
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

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.

Input
The first line of the input contains 4 integers n, a, b, T (1 ≤ n ≤ 5·105, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 109) — the number of photos, time to move from a photo to adjacent, time to change orientation of a photo and time Vasya can spend for watching photo.

Second line of the input contains a string of length n containing symbols 'w' and 'h'.

If the i-th position of a string contains 'w', then the photo i should be seen in the horizontal orientation.

If the i-th position of a string contains 'h', then the photo i should be seen in vertical orientation.

Output
Output the only integer, the maximum number of photos Vasya is able to watch during those T seconds.

Examples

 input
 4 2 3 10
 wwhw
 output
 2
 input
 5 2 4 13
 hhwhh
 output
 4
 input
 5 2 4 1000
 hhwhh
 output
 5
 input
 3 1 100 10
 whw
 output
 0

Note
In the first sample test you can rotate the first photo (3 seconds), watch the first photo (1 seconds), move left (2 second), rotate fourth photo (3 seconds), watch fourth photo (1 second). The whole process takes exactly 10 seconds.

Note that in the last sample test the time is not enough even to watch the first photo, also you can't skip it.

 

思路

明确题意,不可以直接翻阅未看过的(unseen)照片。所以,Vasya必须看第一张(index 0)照片(花费1s)才可以看下一张。

Vasya有四种方式来看照片:

  1. 向右(pre)一直看下去;
  2. 向左(suf)一直看下去;
  3. 在1的过程中反向看回去;
  4. 在2的过程中反向看回去。

其中3、4中提到的“反向看”一次即可,多次无意义。

解题思路:

  1. 判断第一张照片是否有足够时间,否则返回0,程序退出;
  2. 正向看照片,穷举正向看到第i(i <= n n代表照片总数)张照片时,反向看x张照片耗时在总时间之内(x用二分法来算)。

源码

 

Github: https://github.com/GenialX/Codeforces/blob/master/src/Y16/M03/D11/Q1.java

import java.util.Scanner;

/**
 * B. Image Preview
 * http://codeforces.com/contest/650/problem/B
 * 
 * @author GenialX
 * 
 */
public class Q1 {
	
	public static void main(String args[]) throws Exception{
		new Q1();
	}
	
	Scanner in;
	int n;
	int a;
	int b;
	int T;
	String photos;
	int max;
	
	int curT;
	int []pre;
	int []suf;
	int i, j;
	
	public Q1() {
		in = new Scanner(System.in);
		n = in.nextInt();
		a = in.nextInt();
		b = in.nextInt();
		T = in.nextInt();
		photos 	= in.next();
		curT 	= T;
		pre = new int[500005];
		suf = new int[500005];
		
		if(photos.charAt(0) == 'w') {
			curT -= b;
		}
		
		--curT;
		
		if(curT < 0) {
			System.out.println(0);
			return;
		}
		
		
		for(i = 0; i < n; i++) {
			if(i == 0) {
				pre[i] = 0; // 正着读
				suf[i] = 0; // 反着读
			} else {
				pre[i] = pre[i - 1] + cost(i);
				suf[i] = suf[i - 1] + cost(n - i);
			}
		}

		/** 正着看穷举 **/
		for(i = 0; i < n; i++) { if(pre[i] > curT) break; // 当前所耗时间超过剩余时间
			int l = 0; int r = n - 1 - i;
			int tmp = -1;
			while(l <= r) { int mid = ( l + r )>>1;
				if( pre[i] + suf[mid] + i * a <= curT) { // i * a 代表翻转过程中需要翻过已读相片的时间
					tmp = mid;
					l = mid + 1;
				} else {
					r = mid - 1;
				}
			}
			
			if(tmp != -1) {
				max = Math.max(max, tmp + i );
			} else {
				max = Math.max(max, i);
			}
		}
		
		/** 反着看穷举 **/
		for(i = 0; i < n; i++) { if(suf[i] > curT) break;
			int l = 0; int r = n - 1 - i;
			int tmp = -1;
			while(l <= r) { int mid = ( l + r )>>1;
				if( suf[i] + pre[mid] + i * a <= curT) {
					tmp = mid;
					l = mid + 1;
				} else {
					r = mid - 1;
				}
			}
			
			if(tmp != -1) {
				max = Math.max(max, tmp + i);
			} else {
				max = Math.max(max, i);
			}
		}
		
		System.out.println(max + 1);
		
		return ;
	}
	
	public int cost(int i) {
		if(photos.charAt(i) == 'w') {
			return a + b + 1;
		} else {
			return a + 1;
		}
	}
	
}

文章来源:胡旭个人博客 => 【原】Codeforces Round #345 (Div. 1) B Image Preview

转载请注明出处,违者必究!


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...

发表评论

电子邮件地址不会被公开。 必填项已用*标注