1046 Shortest Distance (20 分)

方法1

先用数组记录前缀后,然后减去两者的差值。
由于数组形成的是个环,所以累加和是固定的,反方向的距离实际就等于总长度减去正向的长度。


#include<cstdio>
const int maxn=1e5+5;
int cost[maxn];
int dp[maxn];
int n;
void swap(int& x,int& y){
	int t=x;x=y;y=t;
}
int min(int a,int b){
	return a<b?a:b;
}
int main(){
	scanf("%d",&n);
	int sum=0;
	dp[0]=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&cost[i]);
		sum += cost[i];
		dp[i]= dp[i-1]+cost[i];
	}
	int m,st,ed;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&st,&ed);
		if(st > ed) swap(st,ed);
		int ans =dp[ed-1] - dp[st-1];
		printf("%d\n",min(ans,sum - ans));
	}
	
	return 0;
}

方法2

有点像笨比,最后一个测试点超时了。
这里主要是记录一下如何计算循环链表或数组中的值
17分

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
int cost[maxn];
int n;
void swap(int& x,int& y){
	int t=x;x=y;y=t;
}
int min(int a,int b){
	return a<b?a:b;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&cost[i]);
	}
	cost[0]=cost[n];
	int m,st,ed;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&st,&ed);
		if(st > ed) swap(st,ed);
		int ans1 =0;
		for(int j=st;j<ed;j++){
			ans1 +=cost[j];
		}
		int ans2 =0;
		for(int j=ed;(j+n)%n != st;j++){
			ans2 += cost[(j+n)%n];
		}
		printf("%d\n",min(ans1,ans2));
	}
	
	return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:40
点赞 评论 收藏
分享
zhch7:建议9✌️把学历加黑加粗,如果实在offer可能是觉得佬不会去
投了多少份简历才上岸
点赞 评论 收藏
分享
LazyBreeze:项目尽量体现你对技术的理解和深度,不是说把中间件用一下就完事了,你项目里面提到集群和分布式,你真在服务器上部署过吗,感觉太假了,第二个项目说自己用了微服务的什么组件,只是用了没有自己的思考,很难让面试官注意到你的简历。针对某几个技术点自己多思考一下,考虑一下有没有别的替代方案,可以写一下,即使没有真的实现
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务