2015
04-16

Running relay

The school track-and-field team is taking a running relay race. There are n (2<=n<=104) members in the team. In order to let everybody participate in the race, each member should run at least d (0<=d<=10) meters. Besides that, everyone can run arbitrary distance. The whole length of the track is L (1<=L<=105) meters.

For the ith member in the team, if he is in a good mood, then it takes him ti seconds (1<=ti<=4×104) to run one meter. If he is in a bad mood, then it takes him si (1<=si<=4×104, 1<=ti<=si) seconds to run one meter.

As the coach of the team, you can assign the running distance of each member in advance. Suppose that, it takes S seconds for the team to complete the relay race if all the members are in bad moods and it takes T seconds for the team to complete the relay race if all the members are in good moods. You do want to have a good score. But you don’t want to have a very bad score even if someone is in a bad mood. So you want to know the minimum value of T on condition that S should not be larger than W (1<=W<=2147483647).

The input begins with a line containing an integer, indicating the number of test cases. There are no more than 100 test cases.

For each case, the first line begins with four integers — the above mentioned n, d, L and W. Then n lines follow, each representing a member. Each line contains two integers s and t, meaning that the member spends s seconds to run one meter when he/she is in a bad mood, and spends t seconds to run one meter when he/she is in a good mood.

The input begins with a line containing an integer, indicating the number of test cases. There are no more than 100 test cases.

For each case, the first line begins with four integers — the above mentioned n, d, L and W. Then n lines follow, each representing a member. Each line contains two integers s and t, meaning that the member spends s seconds to run one meter when he/she is in a bad mood, and spends t seconds to run one meter when he/she is in a good mood.

2
2 1 20 141
8 3
6 6
3 8 20 200
8 3
6 6
7 1

88.50
No solution
Hint
In the first case, the first member runs 10.5 meters and the second member runs 9.5 meters. S=8×10.5+6×9.5=141=W, T=3×10.5+6×9.5=88.5. In the second case, every member should run at least 8 meters. But the length of the track is only 20 meters. Because 8×3>20, there is no solution.

1、L-sigma(xi)>=0 ===> sigma(xi)<=L （一开始漏了这个，就变成了一维问题…）

2、sigma(si*xi)+sn*(L-sigma(xi))<=W ===> sigma((si-sn)*xi)<=W-sn*L

max （tn-t1,….ti-tn）*(x1,…xi…)’

1、 (1,1,1…)*(x1….xi…)’<=L

2、 (s1-sn…si-sn…)*(x1…xi…)’<=W-sn*L
(不方便写成一个矩阵，只好分开写)

min (y1,y2)*(L,W-sn*L)’

（y1,y2）*(1,1,1….)

（s1-sn,…si-sn…）
>=(tn-t1…tn-ti…) (这里必须合到一起了==)

y1+y2*(si-sn)>=tn-ti

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
const double oo=1e50,eps=1e-8,pi=acos(-1.0);
using namespace std;
struct point{
double x,y,z,_,d;
}p[200000];
int s[200000],t[200000];
int n,d,L,W,T,u[200000],st[200000];
double WW,LL,tot,Min;
inline double cr(point e,point r) {return e.x*r.y-e.y*r.x;}
inline double dot(point e,point r) {return e.x*r.x+e.y*r.y+e.z*r.z;}
inline void cross(point p,point q,point &e)
{
e.x=p.y*q.z-p.z*q.y;
e.y=p.z*q.x-p.x*q.z;
e.z=p.x*q.y-p.y*q.x;
}
inline void ori(point &a)
{
a._=atan2(a.y,a.x);
a.d=a.z/sqrt(sqr(a.x)+sqr(a.y));
}
inline bool cmp(int i,int j)
{
double tmp=p[i]._-p[j]._;
if (fabs(tmp)>pi/2) return tmp<-eps;
tmp=cr(p[i],p[j]);
if (fabs(tmp)>eps) return tmp>eps;
return p[i].d<p[j].d;
}
inline bool check(point L,point T,point I)
{
point p;
cross(L,T,p);
if (dot(p,I)>-eps) return 1;
return 0;
}
double doit()
{
int tot=0;
++tot,p[tot].x=1,p[tot].y=0,p[tot].z=0;
++tot,p[tot].x=0,p[tot].y=1,p[tot].z=0;
++tot,p[tot].x=-1,p[tot].y=0,p[tot].z=oo;
++tot,p[tot].x=0,p[tot].y=-1,p[tot].z=oo;
for (int i=1;i<=n-1;i++) {
++tot;
p[tot].x=s[i]-s[n];
p[tot].y=1;
p[tot].z=t[i]-t[n];
}
for (int i=1;i<=tot;i++) ori(p[i]),u[i]=i;
sort(u+1,u+tot+1,cmp);
int h,r;
st[h=r=1]=u[1];
for (int i=2;i<=tot;i++) {
if (fabs(cr(p[u[i]],p[u[i-1]]))<eps) continue;
for (;(h<r) && (!check(p[st[r-1]],p[st[r]],p[u[i]]));r--) ;
for (;(h<r) && (!check(p[st[h]],p[st[h+1]],p[u[i]]));h++) ;
st[++r]=u[i];
}
for (;(h<r) && (!check(p[st[r-1]],p[st[r]],p[st[h]]));r--) ;
//    for (;(h<r) && (!check(p[st[h]],p[st[h+1]],p[st[r]]));h++) ;
st[r+1]=st[h];
double ans=oo;
for (int i=h;i<=r;i++) {
point e;
if ((st[i]==3) || (st[i]==4) || (st[i+1]==3) || (st[i+1]==4)) continue;
cross(p[st[i]],p[st[i+1]],e);
e.x/=e.z,e.y/=e.z,e.z=1;
double sum=(WW-s[n]*LL)*e.x+e.y*LL;
ans=min(ans,sum);
}
return -ans;
}
int main()
{
scanf("%d",&T);
for (;T;T--) {
scanf("%d%d%d%d",&n,&d,&L,&W);
LL=L-d*n,WW=W;
tot=0,Min=oo;
for (int i=1;i<=n;i++) {
scanf("%d%d",&s[i],&t[i]);
WW-=s[i]*d;
tot+=d*t[i];
Min=min(Min,(double)s[i]);
}
if (WW<0 || LL<0) {
printf("No solution\n");
continue;
}
if (1==n) {
if (L*s[1]>W) printf("No solution\n");
else printf("%.2lf\n",(double)L*t[1]);
continue;
}
if (Min*LL>WW) {
printf("No solution\n");
continue;
}
double ans=doit()+t[n]*LL+tot;
if (ans<-eps) {
printf("No solution\n");
continue;
}
//        cout<<low<<' '<<lim<<' '<<WW-s[n]*LL<<endl;
printf("%.2lf\n",fabs(ans));
}
return 0;
}

1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

2. #include <cstdio>

int main() {
int n, u, d;
while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
if(n<=u) { puts("1"); continue; }
n-=u; u-=d; n+=u-1; n/=u;
n<<=1, ++n;
printf("%dn",n);
}
return 0;
}

3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)