神奇的75分!特判过了
查看原帖
神奇的75分!特判过了
895690
gghack_Nythix楼主2022/12/19 14:52

看着好像是下面几个wa了

#include <bits/stdc++.h>
using namespace std;
#define MAX (100000 + 7)
long long a[MAX];
long long check(long long x,long long n)//之所以写long long是因为要二分最小和最大 
{
	int ans = 0,tmp = 0;
	for(int i = 1;i <= n;i ++)
	{
		tmp += a[i];
		if(tmp < 0)
		{
			tmp = 0;
		}
		if(tmp >= x)//写了一道题 
		{
			tmp = 0;//初始 
			ans ++;//刷的题+1 
		}
	}
	return ans;
}
int main()
{
	long long n,k,r = 1e18;
	cin >> n >> k;
	for(int i = 1;i <= n;i ++)
	{
		cin >> a[i];
	}
	long long l = 1,mid,ans1 = -1;
	while(l <= r)
	{
		mid = (l + r)/ 2;
		if(check(mid,n) <= k)
		{
			r = mid - 1;
			if(check(mid,n) == k) ans1 = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	if(ans1 == -1)
	{
		cout << -1;
		return 0;
	}
	cout << ans1 << " ";
	ans1 = -1,l = 1,r = 1e18;
	while(l <= r)
	{
		mid = (l + r) / 2;
		if(check(mid,n) >= k)
		{
			l = mid + 1;
			if(check(mid,n) == k) ans1 = mid;
		}
		else
		{
			r = mid - 1;
		}
	}
	cout << ans1 << " ";
	return 0;
}
2022/12/19 14:52
加载中...