社区讨论

为什么差分WA?

P2678[NOIP 2015 提高组] 跳石头参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6hjq1c
此快照首次捕获于
2025/11/20 04:59
4 个月前
此快照最后确认于
2025/11/20 04:59
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define mid (l+r)/2
int len,n,m,a[50001],ans;
bool ok(int x)
{
    int k=0,b[50001]; for (int i=1;i<=n;i++) b[i]=a[i];
    for (int i=1;i<=n;i++) {if (b[i]<x) {k++; b[i+1]+=b[i];}}
    return k<=m;
}
int main()
{
    cin>>len>>n>>m; for (int i=1;i<=n;i++) cin>>a[i];
    a[++n]=len; for (int i=n;i>=1;i--) a[i]-=a[i-1];
    int l=0,r=len;
    while(l<=r) {if (ok(mid)) {ans=mid; l=mid+1;} else r=mid-1;}
    cout<<ans<<endl;
return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...