（EF给我干蒙了，有时间补吧……

A. Contest Start 题意：有n个人比赛，其中第一个在0开始，第二个在x，第i个在（i-1）*x开始，每个人在t时间后结束比赛，每个人的不满意度是他结束比赛时场上开始比赛且尚未完赛的人数，求总不满意度。 思路：t<x时ans为0，t==x时ans为n-1，t>x时我们可以得出在n足够大的时候，满足让一个人不满意的人应该是一个依次向后的排列（如图）。分类讨论初始长度k与n关系。 代码：

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //IO
    cin>>t;
    while(t--)
    {
        ans=0;
        cin>>n>>m>>k;
        if(k<m)ans=0;
        else if(k==m)ans=n-1;
        else
        {
            ll kk=min(n-1,k/m);
            if(kk==n-1)ans=(n*(n-1))/2;
            else
            {
                if(n<kk+1)ans=(n*(n-1))/2;
                else ans=(kk*(kk+1))/2+kk*(n-kk-1);
            }
        }
        cout<<ans<<endl;
    }
}

View Code

（然后发现我想多了，其实思路可以非常简单//XD

B. Love Song 题意：水。 代码：

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //IO
    //cin>>t;
    //while(t--)
    {
        a[0]=0;
        cin>>n>>m;
        string s;
        cin>>s;
        rep(i,1,n)
        {
            if(i)a[i]=a[i-1]+s[i-1]-'a'+1;
        }
        rep(i,1,m)
        {
            ll l,r;
            cin>>l>>r;
            ans=a[r]-a[l-1];
            cout<<ans<<endl;
        }
    }
}

View Code

 

C. Stable Groups 题意：给定n个数和k，x两个正整数，现有n个分值为ai的学生，要求排列后相邻两个学生的差的绝对值不大于x，至多能在序列中插入k个任意分值的学生，最少能把原序列加上新的学生后（可不全加或不加）分为几个满足条件的子序列。 思路：我瞎搞的……数据应该比较水，算是个很好想的贪心，找到每个不满足条件的空缺处，找到此处最少需要几个新学生填补，然后升序填进去。 代码：

map<ll,ll>mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //IO
    cin>>n>>k>>x;
    rep(i,1,n)cin>>a[i];
    sort(a+1,a+1+n);
    rep(i,2,n)
    {
        if(a[i]-a[i-1]>x)
        {
            ll kk=(a[i]-a[i-1]-1)/x;//?
            ans++;
            if(!mp[kk])vis[++tt]=kk;
            mp[kk]++;
        }
    }
    ans++;
    sort(vis+1,vis+tt+1);
    rep(i,1,tt)
    {
        if(k>mp[vis[i]]*vis[i])
        {
            ans-=mp[vis[i]];
            k-=mp[vis[i]]*vis[i];
        }
        else if(k==mp[vis[i]]*vis[i])
        {
            ans-=mp[vis[i]];
            k=0;
            i=tt+1;
        }
        else
        {
            ans-=k/vis[i];
            k=0;
            i=tt+1;
        }
    }
    cout<<ans<<endl;
}

View Code D. PriceFixed 题意：要买n种商品，每种商品要买ai个，每种商品在购买过bi件任意商品后可以打五折，每件商品原价为2，最少需要多少钱。 思路：很明显单纯为了打折而去买多的商品至少需要1+1元，和直接买没区别，那就是直接贪心了。 代码：

bool cmp(node a,node b)
{
    return a.b<b.b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //IO
    cin>>n;
    rep(i,1,n)
    {
        cin>>c[i].a>>c[i].b;
    }
    sort(c+1,c+1+n,cmp);
    ll l=1,r=n;
    while(l<=r)
    {
        if(c[l].b<=cnt)
        {
            ans+=c[l].a;
            cnt+=c[l].a;
            l++;
        }
        else
        {
            ll minn=min(c[r].a,c[l].b-cnt);
            cnt+=minn;
            ans+=2*minn;
            c[r].a-=minn;
            if(c[r].a==0)r--;
        }
    }
    cout<<ans<<endl;
}

View Code /* E. Game with Cards 看着感觉像dp，但搞不出来，结束看有人写的是线段树，有时间再补吧…… */