感觉思路没有错呀,为什么Wa了一大片,求大佬解答!!!
查看原帖
感觉思路没有错呀,为什么Wa了一大片,求大佬解答!!!
1024853
sana_37楼主2023/8/10 23:09
#include<iostream>
using namespace std;
int main()
{
	int N;
	long long C;
	cin >> N >> C;
	//int len = 0;
	long long* arr = new long long[N];
	long long* opt = new long long[N];//前缀和
	
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		if (i == 0)
		{
			opt[i] = arr[i];
		}
		else
		{
			opt[i] = opt[i - 1] + arr[i];
		}
	}
	if (opt[N - 1] <= C)
	{
		cout << opt[N - 1] << endl;
		return 0;
	}
	long long sum = 0;
	long long ans = 0;
	int flag = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		for (int j = i-1; j >= 0; j--)
		{
			sum = arr[i] + opt[j];//当前值加上下一个的前缀和
			if (sum > ans && sum <= C)//满足条件,保留此答案
			{
				ans = sum;
			}
			if (sum < C&&j==i-2)//一开始最多的前缀和都小于C,后面再怎么加也会比现在小
			{
				flag = 1;
				break;
			}
			else if (sum < C)//后面再怎么加的值都比当前的sum小,直接退出
			{
				break;
			}

		}

		if (flag == 1)//找到了,退出
		{
			break;
		}
	}

	cout << ans << endl;

	return 0;
}
2023/8/10 23:09
加载中...