[TYVJ] 4867 天天寄快递

问题描述

天天暑假时帮别⼈寄送快递，经历了⼀个暑假，天天积累了不少数据，想对快递公司进⾏⼀下评分，得到快递公司的质量⽔平。总共有$$n$$家快递公司，编号为$$1 \cdots n$$。现在天天有$$m$$天的寄送快递数据，其中第$$i$$天使⽤第$$e_i$$家快递公司，快递在路上花了$$t_i$$天时间。⼀开始每个快递公司的评分都为0，对于⼀家快递公司，如果⼀个包裹花了$$t_i$$天寄到，那么对这家快递公司的评分贡献为$$2-t_i$$，（如果花的时间超过两天得分就会变成负的啦）。

然⽽事情没有这么简单，如果某⼀天的数据丢掉了，天天为了公平起见就忽略掉这天的数据。于是快递公司联盟决定雇佣⼀个⼩偷，⼩偷可以偷⾛最多$$s$$天的数据，使得每个公司的信⽤得分⾄少增加$$k$$，且所有快递公司的信⽤总和尽量⼤。

若如果被偷以后，⽆法让每个公司的信⽤得分都⾄少增加$$k$$，输出-23333333，否则请你输出被偷后,所有快递公司的信⽤得分的和最多增加多少。

输入格式

第⼀⾏四个整数$$n, m, s, k$$，其中$$1 \leq n, m \leq 100000$$;$$ 0 \leq s \leq m$$;$$0 \leq k \leq 10^9 $$

接下来$$m$$⾏，每⾏两个整数。接下来的第$$i$$⾏为$$e_i$$,$$t_i$$，其中$$1 \leq e_i \leq n$$;$$0 \leq t_i \leq 10^9 $$.

输出格式

一个整数，为题目要求的答案。

测试样例

样例输入

样例输出

样例解释

⼩偷可以偷 4 天的数据，但是⼩偷实际上只偷了第 2,3,4 天的数据，1 号公司获得了 38 分的提升，2 号公司获得了 23 + 28 分的提升，都满⾜了最⼩提升 22 分的要求。

数据规模和约定

对于 30% 的数据，$$ 1 \leq n,m \leq 20$$

对于 100% 的数据，$$1 \leq n,m \leq 200000,$$

思路

贪心

每排一遍序，删去<0的数

代码

#include <bits/stdc++.h>
using namespace std;

const int maxnum=1e6+10;
int n,m,s,k;int now[maxnum];bool vis[maxnum];
struct node
{
    int e,t;
}a[maxnum];

int cmp(node a,node b)
{
    return a.t<b.t;
}

#define out {cout<<"-23333333"<<endl;return 0;}

int main()
{
    cin>>n>>m>>s>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].e>>a[i].t;
        a[i].t=2-a[i].t;
    }
    sort(a+1,a+m+1,cmp);

    int tmp=0;
    for(int i=1;i<=m;i++)
    {
        if(a[i].t>0)    break;
        if(now[a[i].e]<k)
        {
            now[a[i].e]-=a[i].t;
            vis[i]=1;
            tmp++;
        }
    }
    if(tmp>s)   out

    for(int i=1;i<=n;i++)
        if(now[i]<k)    out
    if(tmp!=s)
        for(int i=1;i<=m;i++)
        {
            if(vis[i])  continue;
            if(a[i].t>0 || tmp ==s) break;
            tmp++;
            now[a[i].e]-=a[i].t;
        }
    long long sum=0;
    for(int i=1;i<=n;i++)
        sum+=now[i];
    cout<<sum<<endl;
    return 0;
}

[TYVJ]天天寄快递