想问一下各位佬,C题,离散化后我先求了每点之前所有左端点数和右端点数。然后包含k条线段的最小区间,若i点之前的右端点数有x个,那么他对应区间的左端点,应该是左端点数第一个大于x-k的点,这个思路是错的吗?
代码如下:
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define db double #define il inline #define x first #define y second #define endl '\n' const int N=1e6+5; const int mod=998244353; int a[N],b[N],z[N],y[N]; void solve() { int n,m,k;cin>>n>>m>>k; map<int,int>tru_num,num_tru,mp; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]; mp[a[i]]++,mp[b[i]]++; } int cnt=0; for(auto i:mp) { tru_num[i.first]= ++cnt; num_tru[cnt]= i.first; } for(int i=1;i<=n;i++) { z[tru_num[a[i]]]++; y[tru_num[b[i]]]++; } for(int i=1;i<=cnt;i++) z[i]+=z[i-1],y[i]+=y[i-1]; int ans=0,l=0; for(int i=1;i<=cnt;i++) { if(y[i]>=k) { int t=upper_bound(z+1,z+cnt+1,y[i]-k)-z; ans+=(num_tru[t]-l)*(m-num_tru[i]+1); l=max(num_tru[t],l); } } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int T=1;//cin>>T; while(T--){ solve(); } return 0; }
全部评论
(1) 回帖