锅锅

发表于 |
字数统计: 186 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※※

Description

还有10h就要考试了，蔡老师发现题没有造完，还要x个题需要写标程, y个题需要造数据。蔡老师只能甩锅给网友们，帮他一起造题了。
一共有n个网友，蔡老师发现n恰好是x+y的约数，所以可以把这些锅均匀地分给网友们，也就是每个人接到(x+y)/n个锅。
对于一个第i个网友，写一个标程需要ai的时间，造一个数据需要bi的时间。
为了防止网友们造反，蔡老师希望大家需要花的时间都差不多，也就是花时间最多的人和最少的人的差尽量小。

Solution

要使差值最小，最后所选的一定是一个区间，我们的目的便成了如何去构造一个
满足条件的区间
为了观察区间性质，我们把每个人能给出的情况（（x+y）/n种）全部拿来排序，则最终我们选出一个连续区间，答案就是末端减首端
考虑区间的合法性，约束条件是写标程的人总数要达到x。我们注意在统计连续区间的时候，一个区间内很可能会包含同一个人的不同贡献（对写标程人数），而注意，第二次计入同一个人的贡献时拿来更新此人在计算最终答案时对写标程和造数据拥有的更多选择，即，它使写标程的人数成了一个范围。
只要这个范围包围了x，且一共选了n个人，即是一个可行解

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
const int nn=10000005;
typedef long long ll;
int n,x,y,k,tot=0,rev[nn],aa[nn],bb[nn]; ll ans=0x3f3f3f3f3f3f3f3f;
struct dat{
    int id,k; ll ans;
    friend bool operator<(dat a,dat b){
        return a.ans==b.ans?a.k<b.k:a.ans<b.ans;
    }
}e[nn];
int main(){
    int all=0,i,j,a,b,t;scanf("%d%d%d",&x,&y,&n); k=(x+y)/n; 
    for(i=1;i<=n;i++){
        scanf("%d%d",&a,&b);  aa[i]=a;bb[i]=b;
        for(t=0;t<=k;t++){
            e[++tot]=(dat){i,t,1ll*a*t+1ll*b*(k-t)};
        }
    }
    sort(e+1,e+1+tot); int suml=0,sumr=0;
    for(i=1,j=1;i<=tot;i++){
        while(j<=tot&&!(all==n&&suml<=x&&sumr>=x)){
            a=e[j].id;
            if(!rev[a]) all++,suml+=e[j].k,sumr+=e[j].k;
            else {
                if(aa[a]<=bb[a]) suml--;
                if(aa[a]>=bb[a]) sumr++;
            }
            rev[a]++;j++;
        }
        if(all!=n) break;
        ans=min(ans,e[j-1].ans-e[i].ans); a=e[i].id;
        if(rev[a]==1) suml-=e[i].k,sumr-=e[i].k,all--;
        else {
            if(aa[a]<=bb[a]) suml++;
            if(aa[a]>=bb[a]) sumr--;
        }
        rev[a]--;
    }
    cout<<ans<<endl;
    return 0;
}