搜索求调试
  • 板块P1528 切蛋糕
  • 楼主AK_heaven
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/13 09:46
  • 上次更新2024/7/13 11:05:17
查看原帖
搜索求调试
799877
AK_heaven楼主2024/7/13 09:46
#include <bits/stdc++.h>
#define ll long long
#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)

using namespace std;

const int N = 1500;

ll S[N], a[N], b[N], n, m; // prefix cakes mouth

ll all, tot, was, need, mx;

bool DFS(int i, int lst) {
	if(i == 0) return 1;
	// 可行性优化 
	if(tot - was < need) return 0;
	bool flag = 0;
	L(j, lst, n) {
		if(a[j] >= b[i]) {
			a[j] -= b[i];
			tot -= b[i];
			need -= b[i];
			
			bool wasted = 0;
			if(a[j] < b[1]) {
				was += a[j];
				wasted = 1;
			}
			else if(b[i-1] == b[i]) {
				flag |= DFS(i-1, j);
			}
			else 
			    flag |= DFS(i-1, 1);
			if(wasted) was -= a[j];
			a[j] += b[i];
			tot += b[i];
			need += b[i];
		}
		if(flag) return 1;
	}
	return flag;
}

bool check(int x) {
	need = S[x];
	was = 0;
	tot = all;
	return DFS(x, 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	all = tot = S[0] = 0;
 	cin >> n;
	L(i, 1, n) cin >> a[i], mx = max(mx, a[i]), all += a[i];
	cin >> m;
	L(i, 1, m) cin >> b[i];
	sort(b+1, b+m+1);
	L(i, 1, m) S[i] = S[i-1] + b[i];
	while(b[m] > mx) m--;
	int l = 0, r = m, ans = 0;
//	cout << check(7) << '\n';
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) l = mid+1, ans = mid;
		else r = mid-1;
	}
	cout << ans;
	return 0; 
}

25 pts,有 T 有 wa

2024/7/13 09:46
加载中...