sicily 1419

//从中间跑向两边送牛奶，求最小不满意值 = 每个用户收到牛奶的时间+ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MA = 1001; int f1[MA][MA],f2[MA][MA]; int s[MA]; int l,p,t,n; inline int mn(int a,int b) { return a < b ? a : b; } int main() { //freopen("1.txt","r",stdin); scanf("%d",&t); while( t-- ) { scanf("%d%d",&n,&l); for(int i = 0;i < n;i++) scanf("%d",s+i); s[n++] = l; sort(s,s+n); p = 0; while( s[p] < l ) p++; memset(f1,0x6f,sizeof(f1)); memset(f2,0x6f,sizeof(f2)); f1[p][p] = f2[p][p] = 0; for(int i = p;i >= 0;i--) { for(int j = p;j < n;j++) { if( i < p ) { f1[i][j] = mn( f1[i+1][j] + ( s[i+1] - s[i] ) * ( n - (j-i)),f2[i+1][j] + ( s[j] - s[i] ) * ( n - (j-i))); } if( j > p ) { f2[i][j] = mn( f1[i][j-1] + ( s[j] - s[i] ) *( n - (j-i)),f2[i][j-1] + ( s[j] - s[j-1] ) * ( n - (j-i)) ); } } } cout<<mn( f1[0][n-1] , f2[0][n-1] )<<endl; } return 0; }