Codeforces Round #345 (Div. 2) D. Image Preview 暴力 二分
D. Image Preview
题目连接：
http://www.codeforces.com/contest/651/problem/D
Description
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.
Sample Input
4 2 3 10
wwhw
Sample Output
2
Hint
题意
有n张照片，你看一张照片需要1秒，你滑动照片到左边或者右边，需要a秒，翻转照片需要b秒，问你在T秒内最多看多少张照片
照片必须看，不能跳过。
手机是h的，一直保持着h不变。
题解：
暴力枚举左边看多少张，然后二分右边最多看多少张
暴力枚举右边看多少张，然后二分左边。
具体实现，就当成模拟题去做吧……
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+7;
int n,a,b,T;
string s;
int d[maxn],d2[maxn];
int check(char k)
{
if(k=='w')return 0;
else return 1;
}
int update(int x,int y)
{
if(x+y>1e9)return 1e9+1;
return x+y;
}
int main()
{
scanf("%d%d%d%d",&n,&a,&b,&T);
T+=a;
cin>>s;
int now = 1;
for(int i=0;i<n;i++)
{
if(i!=0)d[i]=d[i-1];
if(check(s[i])!=now)
d[i]=update(d[i],a+b+1);
else
d[i]=update(d[i],a+1);
}
now = 1;
reverse(s.begin(),s.end());
for(int i=0;i<n;i++)
{
if(i!=0)d2[i]=d2[i-1];
if(check(s[i])!=now)
d2[i]=update(d2[i],a+b+1);
else
d2[i]=update(d2[i],a+1);
}
reverse(s.begin(),s.end());
int ans = 0;
for(int i=0;i<n;i++)
{
if(T<d[i])break;
int las = T - d[i];
ans=max(i+1,ans);
if(i==n-1)continue;
if(las<a*i+d2[0])continue;
las-=a*i;
int l=0,r=n-i-2,Ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(d2[mid]<=las)l=mid+1,Ans=mid;
else r=mid-1;
}
ans=max(i+1+Ans+1,ans);
}
if(s[n-1]!=s[0])T-=b;
for(int i=0;i<n-1;i++)
{
if(T<d2[i]+d[0]+a)break;
int las = T - d2[i] - d[0] - a;
ans=max(i+2,ans);
if(las<a*i)continue;
las-=a*i;
las+=d[0];
int l=0,r=n-i-2,Ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(d[mid]<=las)l=mid+1,Ans=mid;
else r=mid-1;
}
ans=max(i+1+Ans+1,ans);
}
cout<<ans<<endl;
}最新文章
- java6
- [Docker] docker 基础学习笔记1（共6篇）
- poj1125最短路
- 【笨嘴拙舌WINDOWS】计时器精度
- （1）quartz集群调度机制调研及源码分析---转载
- Java实现对文件的上传下载操作
- IOS 特定于设备的开发：获取和使用设备姿势（通过手机方向控制3d物体显示）
- grunt安装使用简介
- 模拟红外协议C程序——接收模块
- innerHTML，innerText，outerHTML，outerText，value浅析
- Django 1.11 release note简明解读
- vue初始化项目，构建vuex的后台管理项目架子
- 报错：Maximum call stack size exceeded
- matlab二维绘图学习摘要
- Deep Learning.ai学习笔记_第二门课_改善深层神经网络：超参数调试、正则化以及优化
- ngIf 和 template的结合使用
- MFC信号量使用指南
- tr循环，每行 2个数相加 求出和位第三个数赋值 (http://jsfiddle.net/hgeL44rz/113/)
- 在windows下安装python包管理器pip及使用
- hrabs 首页 新闻，快捷菜单，响应式列表，seliverlight