关于刚才 ABC 的D题,始终 AC 19 WA 2
  • 板块灌水区
  • 楼主Buried_Dream
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/7/2 21:42
  • 上次更新2023/10/27 22:02:56
查看原帖
关于刚才 ABC 的D题,始终 AC 19 WA 2
396974
Buried_Dream楼主2022/7/2 21:42

思路是维护一个前缀和和前缀最小值,然后贪心的找最小值。

ll a[N], b[N];
ll ans = 1e18, qzh[N], c[N];

signed main() 
{
	int n = read(), x = read();
	c[0] = 1e18;
	for(int i = 1; i <= n; i++) {
		a[i] = read(), b[i] = read();
		qzh[i] = qzh[i - 1] + a[i] + b[i], c[i] = min(b[i] * 1ll, c[i - 1]);
	}
	for(int i = 1; i <= n; i++) {
		ll m = qzh[i];
		ans = min(ans, m + c[i] * (x - i));
	}
	cout << ans;
	return 0;
}
2022/7/2 21:42
加载中...