社区讨论
50pts求条,玄关
P3143[USACO16OPEN] Diamond Collector S参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mlhg7kyk
- 此快照首次捕获于
- 2026/02/11 11:06 上周
- 此快照最后确认于
- 2026/02/12 21:50 7 天前
AI都改不出来,求你们了,呜呜呜
CPP#include<bits/stdc++.h>
#define ll long long
#define db double
#define endl '\n'
#define int register int
#define AKIOI ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define AKNOI return 0;
#define db double
using namespace std;
const ll MAXN = 50005;
ll n, k,p,res,dia[MAXN];
bool covered[MAXN];
struct member{ll le,ri,length;}ans[MAXN];
bool cmp(member p,member q){
return p.length>q.length;
}
signed main(){
AKIOI;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>dia[i];
sort(dia+1,dia+n+1);
ll r=1;
for(int l=1;l<=n;l++){
// 修复:不跳过重复左端点,而是复用前一个结果(避免丢失区间)
if(l > 1 && dia[l] == dia[l-1]){
ans[++p] = member{l, ans[p].ri, ans[p].length};
continue;
}
// 双指针找以l为左端点的最大r(O(n)效率)
while(r <= n && dia[r] - dia[l] <= k){
r++;
}
ll ri = r - 1;
ll len = ri - l + 1;
ans[++p] = member{l, ri, len};
}
sort(ans+1,ans+p+1,cmp);
ll max_total = 0;
for(int i = 1; i <= min(p, 200LL); i++){
memset(covered, 0, sizeof(covered));
ll cnt1 = 0;
for(int j = ans[i].le; j <= ans[i].ri; j++){
covered[j] = true;
cnt1++;
}
ll cnt2 = 0;
for(int j = 1; j <= min(p, 200LL); j++){
if(i == j) continue;
ll temp = 0;
for(int k = ans[j].le; k <= ans[j].ri; k++){
if(!covered[k]) temp++;
}
cnt2 = max(cnt2, temp);
}
max_total = max(max_total, cnt1 + cnt2);
}
cout << max_total;
AKNOI;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...