求助,我这个思路哪里错了》就是先找到交换前的最大值的那个分界点,分三种情况进行讨论,求hack代码


using namespace std;

typedef long long ll;
typedef pair<ll, ll>PII;
typedef pair<ll, string>PIS;
const int N = 1e6 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e9 + 7;

ll a[3][N], s[3][N];
int main()
{
	int t;
	cin >> t;
	while(t --){
		int n;
		cin >> n;
		for(int i = 1; i <= 2; i ++)
		{
			for(int j = 1; j <= n; j ++)
			{
				cin >> a[i][j];
				s[i][j] = s[i][j - 1] + a[i][j];
			}
		}
		ll maxs = -2e18, f = 0;
		for(int i = 1; i <= n; i ++)
		{
			if(maxs < s[1][i] + s[2][n] - s[2][i - 1])
			{
				maxs = s[1][i] + s[2][n] - s[2][i - 1];
				f = i;//在哪里转折的
			}
		}
		//转折的地方与其他交换
		ll o1 = -2e18, o2 = -2e18;
		for(int i = 1; i <= f - 1; i ++)
		{
			o1 = max(a[2][i] - a[2][f], o1);
		}
		for(int i = f + 1; i <= n; i ++)
		{
			o2 = max(a[1][i] - a[1][f], o2);
		}
		ll o3 = -2e18, o4 = -2e18;
		for(int i = 1; i <= f - 1; i ++)
		{
			o3 = max(o3, a[2][i] - a[1][i]);
		}
		for(int i = f + 1; i <= n; i ++)
		{
			o4 = max(o4, a[1][i] - a[2][i]);
		}
		cout << maxs + max((ll)0, max(o3 + o4, max(o1, o2))) << endl;
		for(int i = 1; i <= n; i ++)
		{
			s[1][i] = 0;
			s[2][i] = 0;
		}
	}
	
}
全部评论
提供一下我的个人理解,希望对你有帮助,希望大佬们及时更正 https://www.nowcoder.com/users/316764044
点赞 回复 分享
发布于 02-22 13:38 江苏
22
点赞 回复 分享
发布于 02-22 11:50 湖南
给一组hack 1 5 4 2 3 3 -5  -5 3 4 1 5
点赞 回复 分享
发布于 02-22 11:42 湖南
你好,我觉得需要枚举转折的地方,因为有交换这个操作,就不一定是转折在开始最大的地方
点赞 回复 分享
发布于 02-22 11:34 湖南

相关推荐

12-25 16:26
已编辑
河北科技学院 Java
勇敢的牛油不服输:2800-300那不等于2500一个月吗兄弟们
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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