题意：计算机中有一些固定大小的内存，内存越大，处理速度越快。对于一个程序，加入不同的内存空间，处理所需时间不同。现给出m个内存空间，n个程序，对于每个程序程序，有k组数据(s,t)，分别表示当程序 i 在某个内存环境s下对应的运行时间t。当有一个内存空间为si，一个程序的2组数据a,b，满足as<=si<bs，那么这个程序放到该内存中的运行时间是at（取下界）。已知不同的内存空间可以同时运行，同一个内存空间的程序在某一时刻只能有一个在运行。又知道一个程序从提交给计算机到运行结束这段时间为“运行时间”（所有程序在0时刻同时提交）。求出最小平均“运行时间”=总“运行时间”/n个程序，并给出每个程序在哪个内存区内运行（内存区编号1~m），以及该程序在内存区内是从何时开始运行，何时结束的。（保证不会出现程序的最小需求内存>最大内存空间）
分析：
很复杂的题意，直观感觉就是所求的量很多，而且并非直接求最小值，是要具体的把方案求解出来。想到这里应该能确定用图论解决。进一步的，要用什么来处理，排除法也能想到匹配（其实我在刷图论专题= =）。
确定了算法，就明确了方向，一侧必然是n个程序。那么另一侧应该是什么呢？我们求的是平均“运行时间”，那么可行顶标Lx、Ly之和就应该是最小的总“运行时间”。我们先考虑总运行时间应该怎么算呢？假设一个内存空间 i 按顺序运行3个程序a、b、c，那么这个程序总的运行时间Ti=at+(at+bt)+(at+bt+ct)=3*at+2*bt+1*ct
（至此应该都能想到，接下来根据这个式子建模）。
我们发现，a程序虽然是第一个完成，但它受这个内存中程序的数量以及运行次序的影响，实际贡献了3*at的时间。当我们拿到一个程序a，并放入某个内存 i 中。首先根据程序的 k 组数据可以确定at的大小。如果假定这个内存中有x个程序，a程序排在第y个，于是构造一个点(i,x,y)，那么我们就可以确定边权为(x-y+1)*at。
如此构造有何不妥之处呢？
做最佳二分完美匹配，每个程序都对应于一个点(i,x,y)，得到最小值。会不会不合常理呢？会的...因为是在交错树上沿等边增广，这里每次调整后，都必然出现许多等边（(x-y+1)的大小同时受x和y影响），虽然调整交错树可能会出现多条等边，但那是巧合（数据相等），而非必然。这种必然导致的就是出现了大量的符合最小值的方案，一个任务，可以匹配点(i,x,y)，也可以匹配点(i,(x+1),(y+1))，反正都在内存 i 内，at为定值。而这种任意分配是不合理的，因为最后无法确定顺序：一个内存中，若有x个程序，它的(i,x,1)可能都已经匹配，但是本该与(i,x,2)(i,x,3)匹配的点却与(i,(x-1),1)(i,(x-1),2)匹配。
建模失败了，那么有什么可取之处？该如何改进呢？
先找问题：1、点的构造决定了边权(x-y+1)*at，x、y同时影响是等边过多；2、时间复杂度高：一侧有S=n个点，一侧有T=m*n*n=mn2个点，所以总复杂度S*T*(S+T)=m2n5=10的10次方 = =
重新建点，将x,y两个变量简化为一个变量，观察式子Ti=3*at+2*bt+ct，从后往前逐次+1；又边权(x-y+1)*at 中，(x-y+1)本身就表示的是系数，也可以理解为倒数第几个。于是，新的构点取(i,p)：在第 i 个内存中以倒数第p个的身份出现，边权就是p*at。
同样做最佳完美匹配。已知一种完美匹配是任意的，不仅不一定是最佳，而且不一定不合理。但是最佳二分完美匹配，一定是合理的。因为(i,p)与权值p*at相互唯一对应，杜绝了之前多条等边的情况。又有，若在内存 i 中有3个程序a,b,c，分别对应( i,1)( i,2)( i,4)，必然不是最佳，c对应于( i,3)有“更佳”的权值3*ct。再考虑复杂度，S=n，T=m*n,总复杂度S*T*(S+T)=m2n3=10的7次方，可以接受。
注意：
1、S,T两侧的数组因为点数的不同，要分开处理。
2、关于n个程序与m*n个点( i,p),究竟放那一侧，我选择n个程序在S侧。其实若放T侧，貌似可以直接顺序找到每个程序对应的点( i,p)，但还要处理每个程序在内存中的具体时间，复杂度上是相同的。
3、我这样处理其实也存在弊端，这是另一种（n个点在T侧）所能避免的，真亏我能想出来。
固定内存 i ，查找p，从1找到第一个为0的点之前截止，这些点对应的 left[] 就是放在内存 i 中的程序编号。但可能n个程序都在同一个内存中，所以p的上界要定在(n+1)而不是n；这又引发了另一个问题：若n个程序都在最后一个内存中，所找到的(n+1)对应的点是第(m*n+1)个点，超出了既定的数据范围，若初始化右侧数据只是[1,m*n]的话，(m*n+1)这个点会访问到之前的数据。
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 #define clr(a,m) memset(a,m,sizeof(a)) 6 #define rep(i,a,b) for(int i=a;i<=b;i++) 7 #define rrep(i,a,b) for(int i=a;i>=b;i--) 8 using namespace std; 9 10 const int MAXN=55; 11 const int MAXM=11; 12 const int INF =1e9; 13 14 struct Point{ 15 int c,t; 16 Point(){} 17 Point(int _c,int _t):c(_c),t(_t){} 18 bool operator < (const Point res)const { 19 return c<res.c; 20 } 21 }; 22 23 struct Run{ 24 int num,l,r; 25 Run(){} 26 Run(int _num,int _l,int _r):num(_num),l(_l),r(_r){} 27 }run[MAXN]; 28 int time[MAXM]; 29 30 int mem[MAXM],gap[MAXN][MAXN*MAXM];//数组忘记改大小了 31 vector<Point>p[MAXN]; 32 33 int n,m,cnt; 34 int Lx[MAXN],S[MAXN]; 35 int Ly[MAXN*MAXM],T[MAXN*MAXM],left[MAXN*MAXM],slack[MAXN*MAXM]; 36 37 void init() 38 { 39 rep(i,1,n) 40 p[i].clear(); 41 } 42 43 void read() 44 { 45 init(); 46 rep(i,1,m) 47 scanf("%d",&mem[i]); 48 rep(i,1,n){ 49 int k,c,t; 50 scanf("%d",&k); 51 rep(j,1,k){ 52 scanf("%d%d",&c,&t); 53 p[i].push_back(Point(c,t)); 54 } 55 } 56 rep(i,1,n){ 57 int sz=p[i].size(); 58 rep(j,1,m){ 59 int tt; 60 if(mem[j]<p[i][0].c) 61 tt=INF; 62 else{ 63 int x=upper_bound(p[i].begin(),p[i].end(),Point(mem[j],0))-p[i].begin(); 64 tt=p[i][x-1].t; 65 } 66 67 rep(p,1,n){ 68 if(tt==INF)gap[i][(j-1)*n+p]=-INF; 69 else gap[i][(j-1)*n+p]=-p*tt; 70 } 71 } 72 } 73 } 74 75 bool match(int u) 76 { 77 S[u]=true; 78 rep(v,1,n*m) 79 if(!T[v]){ 80 int tmp=Lx[u]+Ly[v]-gap[u][v]; 81 if(tmp==0){ 82 T[v]=true; 83 if(!left[v]||match(left[v])){ 84 left[v]=u; 85 return true; 86 } 87 }else slack[v]=min(slack[v],tmp); 88 } 89 return false; 90 } 91 92 void update() 93 { 94 int a=INF; 95 rep(v,1,n*m)//!! 96 if(!T[v]) 97 if(a>slack[v]){ 98 a=slack[v]; 99 } 100 rep(i,1,n) 101 if(S[i])Lx[i]-=a; 102 rep(i,1,n*m)//!! 103 if(T[i])Ly[i]+=a; 104 105 } 106 107 void KM() 108 { 109 rep(i,1,n){ 110 Lx[i]=-INF; 111 rep(j,1,n*m) 112 if(Lx[i]<gap[i][j]){ 113 Lx[i]=gap[i][j]; 114 } 115 } 116 rep(i,1,n*m+1) 117 left[i]=Ly[i]=0; 118 119 rep(i,1,n){ 120 rep(j,1,n*m) 121 slack[j]=INF; 122 while(1) 123 { 124 rep(j,1,n) 125 S[j]=0; 126 rep(j,1,n*m) 127 T[j]=0; 128 if(match(i)) 129 break; 130 else{ 131 update(); 132 } 133 } 134 } 135 } 136 137 void print() 138 { 139 printf("Case %d ",++cnt); 140 141 int ans=0; 142 rep(i,1,n) 143 ans+=Lx[i]; 144 rep(i,1,n*m) 145 ans+=Ly[i]; 146 printf("Average turnaround time = %.2f ",-ans*1.0/n); 147 148 clr(time,0); 149 rep(i,1,m){ 150 int sz; 151 rep(p,1,n+1)//!会不会全都在同一个内存区？放在最后一个内存区，找到的+1会越界找到上一组数据 152 if(left[(i-1)*n+p]==0){ 153 sz=p-1; 154 break; 155 } 156 rrep(p,sz,1){ 157 int x=left[(i-1)*n+p]; 158 run[x]=Run(i,time[i],time[i]-gap[x][(i-1)*n+p]/p); 159 time[i]-=gap[x][(i-1)*n+p]/p; 160 } 161 } 162 rep(i,1,n) 163 printf("Program %d runs in region %d from %d to %d ",i,run[i].num,run[i].l,run[i].r); 164 } 165 166 int main() 167 { 168 cnt=0; 169 while(~scanf("%d%d",&m,&n)) 170 { 171 if(!n&&!m) 172 return 0; 173 if(cnt)puts(""); 174 read(); 175 KM(); 176 print(); 177 } 178 return 0; 179 } 180 /* 181 2 4 182 40 60 183 1 35 4 184 1 20 3 185 1 40 10 186 1 60 7 187 2 2 188 20 40 189 2 20 100 40 2 190 2 20 100 40 3 191 */