2017 国庆湖南 Day6
期望得分：100+100+60=260
实际得分：100+85+0=185
二分最后一条相交线段的位置
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define N 100001 int 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<cstdio> #include<cstring> #include<queue> #define N 25 using 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<int>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]]<d[now]+val[i]) { d[to[i]]=d[now]+val[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<cstdio> #include<algorithm> 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]<now[k]) { for(int h=0;h<8;h++) now[(h+j)%24]-=rest[j]; sum+=rest[j];rest[j]=0; } else { int cut=now[k]; for(int h=0;h<8;h++) now[(h+j)%24]-=cut; rest[j]-=cut;sum+=cut; } j--; } if(now[k]) continue; bool f=true; for(int i=k+1,t=1;t<=23;t++,i++) { if(i==24) i=0; if(now[i]<=0) continue; j=i; cnt=0; while(now[i] && cnt<8) { if(j==-1) j=23; cnt++; if(rest[j]<now[i]) { for(int h=0;h<8;h++) now[(h+j)%24]-=rest[j]; sum+=rest[j];rest[j]=0; } else { int cut=now[i]; for(int h=0;h<8;h++) now[(h+j)%24]-=cut; rest[j]-=cut,sum+=cut; } j--; } if(now[i]) { f=false; break; } } if(f) ans=min(ans,sum); } printf("%d\n",ans==1e9 ? -1 : ans); } }