当前位置：首页 > article >正文

2025 河北ICPC( D. 金泰园（二分）-- C.年少的誓约(公式转化))

article 2025/6/26 17:24:29

文章目录

2025 河北ICPC
- D. 金泰园（二分）
- C.年少的誓约(公式转化)
- 总结

2025 河北ICPC

题目链接：

Attachments - The 9th Hebei Collegiate Programming Contest - Codeforces

sdccpc20250522 - Virtual Judge

赛时：5道

D. 金泰园（二分）

没想到二分，偶然间听到，还没想出怎么二分，此题借助题解和其他人代码。

二分对象是谁？

本题，如果二分答案即和的最小值，check函数怎么写呢？

似乎解决不了。那还可以二分什么呢？

二分找到所选择的k对中的最大差值 ，

check函数怎么写？

对于x ，如果差值小于等于x的对数大于等于 k ，说明最小差值小于等于 x。
怎么查找差值小于等于x的对数

对于排好序的数组，如果a[i+p]-a[i]<=x,p是满足条件的最大值，

那么对于a[i+1+t]-a[i+1]<=x 满足条件的 t 一定大于 p。

易知，所有满足的下标值是不断增大的，最大为 n 。

循环计算每个a[i],所构成的对数。
已知x,再通过前缀和计算差值小于等于 x 的和
用cnt记录满足条件的对数有多少个
最大差值为 x ，不代表所有差值等于 x 都需要选择。用cnt-k,就是多计算的。

int a[N],n,k,pre[N];
bool check(int x)
{int sum=0,p=1;for(int i=1;i<=n;i++){while(p<=n&&a[p]-a[i]<=x) p++;sum+=p-i-1;}return sum>=k;
}
void solve()
{cin>>n>>k;fir(i,1,n)cin>>a[i];sort(a+1,a+n+1);int l=1,r=1e8;//找到前k个的最大差值while(l<r){int mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}fir(i,1,n)pre[i]+=pre[i-1]+a[i];int ans=0,cnt=0,p=1;for(int i=1;i<=n;i++){while(p<=n&&a[p]-a[i]<=l)p++;ans+=pre[p-1]-pre[i]-a[i]*(p-i-1);cnt+=p-i-1;//计算有几个>=l}ans-=(cnt-k)*l;//减去多余的cout<<ans;
}

C.年少的誓约(公式转化)

请添加图片描述

有几个坑：

n*x<m ,输出NO。不然可能WA/RE
数据范围：__int128

对所有的c-b*k进行排序，按顺序分配 x , x , x , m%x , 0 , 0 , 0

int a[N];
void solve()
{ int n,m,k,x;cin>>n>>m>>k>>x;__int128 sum=0,ans=0;fir(i,1,n){int xx,yy;cin>>xx>>yy;a[i]=yy-k*xx;      sum+=xx*yy;}  if(n*x<m){cout<<"NO\n";return;}  int f=m/x,g=m%x;ans+=(__int128)x*x*k*f+(__int128)g*g*k;sort(a+1,a+n+1,greater<int>());fir(i,1,f){ans+=(__int128)a[i]*x;}ans+=(__int128)a[f+1]*g;if(ans<=sum)cout<<"NO\n";else cout<<"YES\n";}