Codeforces Round #690 (Div. 3)（D,E,F）

因为离散数学欠了很多课，作业没交，估计又会被记名一次，害，鸽了一场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;
}