社区讨论

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 条回复,欢迎继续交流。

正在加载回复...