这两份代码哪里不同呢?一个过一个不过,哪位大佬解释解释趴!
查看原帖
这两份代码哪里不同呢?一个过一个不过,哪位大佬解释解释趴!
686187
pumaway楼主2022/8/22 17:43

AC的代码长这样

// I'm gagapuma
// Problem: P1182 数列分段 Section II
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1182
// Memory Limit: 125 MB
// Time Limit: 1000 ms


#include <bits/stdc++.h>
using namespace std;
//#define MAXN 100010
#define rep(i,a,n) for (ll i=a;i<=n;++i)
#define per(i,a,n) for (ll i=n;i>=a;--i)
#define INF 1000000000
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pob pop_back
#define all(x) (x).begin(),(x).end()
#define ent cout<<'\n'
//const int N = ;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

ll n,m;
ll a[1000010];

bool check(ll mid)
{
	ll sum=0,cnt=0;
	rep(i,1,n)
	{
		if(sum+a[i]<=mid)
			sum+=a[i];
		else
		{
			cnt++;
			sum=a[i];
		}
	}
	cnt++;
	return cnt<=m;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	
	ll l=0,r=0;
	cin>>n>>m;
	rep(i,1,n) cin>>a[i],l=max(l,a[i]),r+=a[i];

	if(n==m) 
	{
		cout<<l;
		return 0;
	}

	while(l<r)
	{
		ll mid=l+r>>1;
		if(check(mid)) 
			r=mid;
		else
			l=mid+1;
	}
	
	cout<<l<<endl;

	return 0;
}

wa代码长这样,哪里错了呀

// I'm gagapuma
// Problem: P1182 数列分段 Section II
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1182
// Memory Limit: 125 MB
// Time Limit: 1000 ms


#include <bits/stdc++.h>
using namespace std;
//#define MAXN 100010
#define rep(i,a,n) for (ll i=a;i<=n;++i)
#define per(i,a,n) for (ll i=n;i>=a;--i)
#define INF 1000000000
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pob pop_back
#define all(x) (x).begin(),(x).end()
#define ent cout<<'\n'
//const int N = ;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

ll n,m;
ll a[1000010];

bool check(ll mid)
{
	ll sum=0,cnt=0;
	rep(i,1,n)
	{
		if(sum+a[i]<=mid)
			sum+=a[i];
		else
		{
			cnt++;
			sum=a[i];
		}
	}
	cnt++;
	return cnt<=m;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	
	ll l=0,r=0;
	cin>>n>>m;
	rep(i,1,n) cin>>a[i],r+=a[i];

	while(l<r)
	{
		ll mid=l+r>>1;
		if(check(mid)) 
			r=mid;
		else
			l=mid+1;
	}
	
	cout<<l<<endl;

	return 0;
}









球球!!感谢

2022/8/22 17:43
加载中...