因为离散数学欠了很多课,作业没交,估计又会被记名一次,害,鸽了一场cf,今天补了D,E,F,题解就不详细写了,贴个代码。。。。(真不是想水的,生活一言难尽)
D.真就瞎搞搞就出来了,好像没有坑(但是自己代码长,估计有更简单的方法,没时间去看了)
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; #define ll long long int a[N]; int res; int n; int sol(int x) { int temp=res/x; int ans=0; int k=temp; for(int i=1;i<=n;i++) { if(a[i]>temp) { ans=(int)1e9; break; } else if(a[i]==temp&&k!=temp) { ans=(int)1e9; break; } else if(a[i]==temp) { k=temp; } else { ans++; k-=a[i]; if(k==0) { ans--; k=temp; } } } if(k!=temp&&k!=0) ans=(int)1e9; return ans; } int main() { int t; cin>>t; while(t--) { cin>>n; int maxn=-1; res=0; for(int i=1;i<=n;i++) { cin>>a[i]; res+=a[i]; maxn=max(maxn,a[i]); } int k=n; int ans=(int)1e9; while(k>=1) { ans=min(ans,sol(k)); k--; } cout<<ans<<endl; } return 0; }
E.E1和E2一个道理,来个组合数模板就行,贴个E1
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; #define ll long long int a[N]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+1+n); ll sum=0; int l=1; for(int i=1;i<=n;i++) { while(a[i]-a[l]>2) { l++; } sum+=(ll)(i-l)*(i-l-1)/2; } cout<<sum<<endl; } return 0; }
F.这个题画画图,就是求每个区间外的区间个数的最小值,离散化就ok(去重都不需要hhhh)
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; #define ll long long struct node{ int l; int r; }; struct node p[N]; int main() { int t; cin>>t; vector<int>l; vector<int>r; while(t--) { int n; cin>>n; l.clear(); r.clear(); for(int i=1;i<=n;i++) { cin>>p[i].l>>p[i].r; l.push_back(p[i].l); r.push_back(p[i].r); } sort(l.begin(),l.end()); sort(r.begin(),r.end()); int res=(int)1e9; for(int i=1;i<=n;i++) { int tl=p[i].l; int tr=p[i].r; //找左端点大于它的右端点 int temp=0; int k1=upper_bound(l.begin(),l.end(),tr)-l.begin(); temp+=n-k1; int k2=lower_bound(r.begin(),r.end(),tl)-r.begin(); temp+=k2; //cout<<tl<<' '<<tr<<' '<<k1<<' '<<k2<<endl; res=min(res,temp); //它之外的区间 } cout<<res<<endl; } return 0; }