codeforces 1073 C. Vasya and Robot 1073D. Berland Fair（两个思维题）

链接：http://codeforces.com/contest/1073

C题：

题意：给你一串操作，你可以修改其中的操作使得小明从0 0 走到x y ，定义最小操作次数为最远两次修改操作的距离，你要求出最小操作次数或者输出不可能。

思路： 没啥疑问，直接二分judge就可以了。

D题：

题意：有n个糖果店，排成一个圈小明有T元钱，然后循环着走，走到的商店如果能买得起一个糖果就买不然就跳过。问最多买多少糖果。

思路： 脑子里蹦出来的第一个思路就是前缀+ 二分，但是还是会TLE，然后可以发现其实如果某些糖果店在某一时刻已经买不起糖果了，那么肯定后边所有的时刻都不用考虑该糖果店了，然后想着用线段树维护，但是还是比较麻烦，其实就是一个思维题，既然我在当前时刻已经买不起该店的糖果，那么我肯定不会将这个店考虑在内，然后就直接统计要考虑的店铺，然后统计sum，直接求cnt，然后乘乘除除加加减减就可以。

C题代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =200005;
char s[N];
int cntz,cnty,cnts,cntx;
int tmpz,tmpy,tmps,tmpx;
int c[5];
int aimx,aimy;
int n;
int isok(int zuo,int you,int shang,int xia,int res)
{
you-=zuo;
shang-=xia;
int xx=abs(aimx-you);
int yy=abs(aimy-shang);
res-=xx;
res-=yy;
if(res<0) return 0;
if(res%2==0) return 1;
return 0;
}
int jud(int mid)
{
memset(c,0,sizeof(c));
for(int i=1;i<=mid;i++)
{
if(s[i]=='L') c[1]++;
else if(s[i]=='R') c[2]++;
else if(s[i]=='U') c[3]++;
else if(s[i]=='D') c[4]++;
}
tmpz=cntz-c[1];
tmpy=cnty-c[2];
tmps=cnts-c[3];
tmpx=cntx-c[4];
if(isok(tmpz,tmpy,tmps,tmpx,mid)) return 1;
for(int i=2;i+mid-1<=n;i++)
{
if(s[i+mid-1]=='L') c[1]++;
else if(s[i+mid-1]=='R') c[2]++;
else if(s[i+mid-1]=='U') c[3]++;
else if(s[i+mid-1]=='D') c[4]++;
if(s[i-1]=='L') c[1]--;
else if(s[i-1]=='R') c[2]--;
else if(s[i-1]=='U') c[3]--;
else if(s[i-1]=='D') c[4]--;
tmpz=cntz-c[1];
tmpy=cnty-c[2];
tmps=cnts-c[3];
tmpx=cntx-c[4];
if(isok(tmpz,tmpy,tmps,tmpx,mid)) return 1;
}
return 0;
}
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
scanf("%d %d",&aimx,&aimy);
for(int i=1;i<=n;i++)
{
if(s[i]=='U') cnts++;
else if(s[i]=='D') cntx++;
else if(s[i]=='L') cntz++;
else if(s[i]=='R') cnty++;
}
int l=0,r=n,ans=-1,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(jud(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(ans==-1)
{
printf("-1n");
}
else
{
printf("%dn",ans);
}
return 0;
}

D题代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =200005;
ll a[N];
ll sum[N];
int n;
ll res;
int main()
{
scanf("%d %lld",&n,&res);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
ll ans=0;
while(res>0)
{
ll cnt=0;
ll sum=0;
for(int i=1;i<=n;i++)
{
if(sum+a[i]<=res)
{
cnt++;
sum+=a[i];
}
}
if(cnt==0) break;
//
printf("res %lld sum %lld cnt %lldn",res,sum,cnt);
ll cc=res/sum;
res-=cc*sum;
ans+=cc*cnt;
}
cout<<ans<<endl;
return 0;
}

最后

以上就是个性天空为你收集整理的codeforces 1073 C. Vasya and Robot 1073D. Berland Fair（两个思维题）的全部内容，希望文章能够帮你解决codeforces 1073 C. Vasya and Robot 1073D. Berland Fair（两个思维题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。