期望得分：100+100+60=260

实际得分：100+85+0=185

 

二分最后一条相交线段的位置

#include
      
       #include
       
        #include
        
         using namespace std;#define N 100001int x[N],y[N];struct node{    int b;    double k;}Point[N];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int main(){    freopen("geometry.in","r",stdin);    freopen("geometry.out","w",stdout);    int n; read(n);    for(int i=1;i<=n;++i) read(x[i]);    for(int i=1;i<=n;++i) read(y[i]);    sort(x+1,x+n+1);    sort(y+1,y+n+1);    for(int i=1;i<=n;i++)    {        Point[i].b=y[i];        Point[i].k=-y[i]*1.0/x[i];    }    int m; read(m);    int a,b; double g;    int l,r,mid,ans;    while(m--)    {        read(a); read(b);        g=1.0*b/a;        l=1;r=n; ans=0;        while(l<=r)        {            mid=l+r>>1;            if(Point[mid].b/(g-Point[mid].k)<=a) ans=mid,l=mid+1;            else r=mid-1;        }        printf("%d\n",ans);    }}
        
       
      

 

 

 

差分约束

设s[i]表示前i个时刻实际招的人数

那么可得约束条件：

a[i]<=s[i]-s[i-7]<=b[i]  i>=7

a[i]<=s[i]+s[23]-s[16+i]<=b[i]  i<7

0<=s[i]-s[i-1]<=b[i]

 

第二个式子中含有3个未知数

只有两个与i有关

设s[23]=T

那么枚举T，判断当前情况是否有解即可

#include
      
       #include
       
        #include
        
         #define N 25using namespace std;int a[N],b[N];int front[N],nxt[81],to[81],tot,val[81];int d[N];bool vis[N];void add(int u,int v,int w){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;}bool spfa(){    queue
         
          q;    memset(vis,false,sizeof(vis));    memset(d,-63,sizeof(d));    d[0]=0; vis[0]=true;    q.push(0);    int now;    while(!q.empty())    {        now=q.front(); q.pop(); vis[now]=false;            for(int i=front[now];i;i=nxt[i])            if(d[to[i]]
          
           1000) return false;                if(!vis[to[i]]) vis[to[i]]=true,q.push(to[i]);            }    }    return true;}bool solve(int t){    memset(front,0,sizeof(front)); tot=0;    for(int i=8;i<24;i++)     {        add(i-7,i+1,a[i]);    //    printf("%d %d %d\n",i-7,i+1,a[i]);    }    for(int i=0;i<=7;i++)     {    //    printf("%d %d %d\n",i+17,i+1,a[i]-t);        add(i+17,i+1,a[i]-t);    }    for(int i=0;i<24;i++)     {    //    printf("%d %d\n",i,i+1);        add(i,i+1,0);    }    for(int i=0;i<24;i++)     {    //    printf("%d %d %d\n",i+1,i,-b[i]);        add(i+1,i,-b[i]);    }    add(0,24,t); add(24,0,-t);    return spfa();}int main(){    freopen("cashier.in","r",stdin);    freopen("cashier.out","w",stdout);    int T,ans;    scanf("%d",&T);    while(T--)    {        for(int i=0;i<24;i++) scanf("%d",&a[i]);        for(int i=0;i<24;i++) scanf("%d",&b[i]);        ans=0;        while(1)        {            if(++ans>1000) { ans=-1; break; }            if(solve(ans))   break;         }        printf("%d\n",ans);    }}
          
         
        
       
      

 

 

 

考场85分贪心

枚举时刻i，作为首先招人满足的时刻

从 它即它往前7个点， 招人，招的人时刻尽可能的靠后

满足它之后，枚举j 到 i-1 再 同样的方法招人

 

此贪心成立的前提是，存在一个时刻招的人=min（a[i],b[i]）

但最优解可能不是这样

假设前面招了x1、x2、x3……个人

最后面招了y个人

这个y会覆盖前面的x1、x2、x3……

 

#include
      
       #include
       
        using namespace std;int need[25],have[25];int now[25],rest[25];int main(){    freopen("cashier.in","r",stdin);    freopen("cashier.out","w",stdout);    int T;    scanf("%d",&T);    int ans;    while(T--)    {        ans=1e9;        for(int i=0;i<24;i++) scanf("%d",&need[i]);        for(int i=0;i<24;i++) scanf("%d",&have[i]);        for(int k=0;k<24;k++)        {            if(!need[k]) continue;            for(int i=0;i<24;i++) rest[i]=have[i],now[i]=need[i];            int j=k,cnt=0,sum=0;            while(now[k] && cnt<8)            {                if(j==-1) j=23;                cnt++;                if(rest[j]
       
      

 

 就是这个