codeforces 1555 C. Coin Rows (暴力+前缀和)

题目

思路:主要注意看一个条件只有两行,且只能向右或向下走,那Alice只有N种移动情况,从第一列就开始下移再往右,先右行至第二列再下移往右,先行至第三列再下移…
而对于每种情况Bob实际上只会从两种情况选一种最大的,一种是只取第一行中Alice没走过的,一种是第二行中Alice没走过的,看下面例子


Alice是蓝色线,Bob贪心之下选的是Max(6,5+2)=7。最后的答案只要把Alice的所有情况都遍历一遍,取所有情况的最小即可(注意用前缀和优化),细节看代码。

#include<iostream>
#include<math.h>

using namespace std;
typedef long long ll;

const int Max = 1e6 + 5;
ll a[Max], b[Max];

int main()
{
   
	int t;cin >> t;
	while (t--)
	{
   
		int n;cin >> n;

		for (int i = 1;i <= n;i++)
		{
   
			cin >> a[i];
			a[i]+= a[i - 1];
		}
		for (int i = 1;i <= n;i++)
		{
   
			cin >> b[i];
			b[i] += b[i - 1];
		}

		ll mi = 1e16+5;
		for (int i = 1;i <= n;i++)
		{
   
			mi = min(mi, max(a[n] - a[i], b[i - 1]));
		}

		cout << mi << endl;
	}
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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