您的位置:首页 > 新闻 > 热点要闻 > 建设局是干什么的_ppt模板哪里可以免费下载_惠州seo按天计费_安卓优化大师app

建设局是干什么的_ppt模板哪里可以免费下载_惠州seo按天计费_安卓优化大师app

2025/4/11 13:23:23 来源:https://blog.csdn.net/mahuatengdediedi/article/details/146986263  浏览:    关键词:建设局是干什么的_ppt模板哪里可以免费下载_惠州seo按天计费_安卓优化大师app
建设局是干什么的_ppt模板哪里可以免费下载_惠州seo按天计费_安卓优化大师app

AB略

C

答案没有单调性,无法用二分答案写。b比a多的得分=s1*0+s2*1+.......+sn*(n-1),s代表这一段中b比a多的数量。这里s的处理可以想到用前缀和来,于是得到(s1-0)*0+(s2-s1)*1+(s3-s2)*2......+(sn-sn-1)*(n-1)=-s1-s2-s3.....+sn*(n-1),这里还是没办法确定n的值,毕竟sn*(n-1)很难确定。于是可以想到后缀和。(s1-s2)*0+(s2-s3)*1+(s3-s4)*2.....sn*(n-1)=s2+s3+....+sn。预处理出所有位置的后缀和降序排序,大于k停止即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,k,s[N],sum;
char c[N];
void init()
{sum=0;
}
void solve()
{cin>>n>>k;init();for(int i=1;i<=n;i++)cin>>c[i];s[n+1]=0;for(int i=n;i>=1;i--){if(c[i]=='1') s[i]=s[i+1]+1;else s[i]=s[i+1]-1;}sort(s+2,s+n+1);for(int i=n;i>=2;i--){sum+=s[i];if(sum>=k) {cout<<n-i+2<<endl; return ;}}cout<<-1<<endl;
}
signed main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--) solve();
}

D

对于每一段来说,找到所有完全包含这一段的段的交集再减去这一段剩下的整数数量。先将左端点升序相等时再右端点降序排序,这样按顺序处理每个段时,可以保证它的所有预言段都处理完了,利用set可知道它的所有预言段右端点的最小值,减去这个段的右端点。在按照这个逻辑处理左端点,左右相加就是答案。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,ll[N],rr[N],bj[N];
struct node{int l,r,id;
}a[N],b[N];
bool cmp(node x,node y)
{if(x.l==y.l) return x.r>y.r;return x.l<y.l;
}
bool cmp1(node x,node y)
{if(x.r==y.r) return x.l<y.l;return x.r>y.r;
}
void init()
{for(int i=1;i<=n;i++)ll[i]=rr[i]=bj[i]=0;
}
void solve()
{cin>>n;init();multiset<int> s;for(int i=1;i<=n;i++){cin>>a[i].l>>a[i].r;a[i].id=i;b[i].l=a[i].l;b[i].r=a[i].r;b[i].id=i;}if(n==1) {cout<<0<<endl; return ;}sort(a+1,a+n+1,cmp);for(int i=2;i<=n;i++)if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r) bj[a[i].id]=bj[a[i-1].id]=1;s.insert(a[1].r);for(int i=2;i<=n;i++){multiset<int>::iterator it;it=s.lower_bound(a[i].r);if(it!=s.end()) rr[a[i].id]=*it-a[i].r;s.insert(a[i].r);}sort(b+1,b+n+1,cmp1);s.clear();s.insert(-b[1].l);for(int i=2;i<=n;i++){multiset<int>::iterator it;it=s.lower_bound(-b[i].l);if(it!=s.end()) ll[b[i].id]=*it+b[i].l;s.insert(-b[i].l);}for(int i=1;i<=n;i++)if(bj[i]) cout<<0<<endl;else cout<<ll[i]+rr[i]<<endl;
}
signed main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--) solve();
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com