Mice and Holes CodeForces

Mice and Holes CodeForces - 797F

题意：有n只老鼠和m个洞，都在一个数轴上，老鼠坐标为x[1],...,x[n]，洞的坐标为p[1],...,p[m]，每个洞能容纳的老鼠为c[1],...,c[m]，问所有老鼠都躲到洞里后每只老鼠跑的距离之和的最小值。

分析：

如果不给出洞和老鼠的顺序的话，就需要集合操作，基本就是枚举，很慢不考虑。

因此，按坐标顺序排序洞和老鼠，然后定义状态：ans[i][j]表示前i个洞放前j个老鼠最小距离和。

这么做是由于如果有老鼠跑的路线交叠了，那么就一定不是最好的答案。而先排序后这么定义状态，就隐含了只能是前i-1个洞放前k个老鼠，然后第i个洞放第k+1到第j个老鼠，路线不交叠。

（以下部分自己想不到）

然而实际做的时候不一定能想到，这时一定要大胆尝试（比如试一试排序，很可能一排序就能定义出状态了）。

那么ans[i][j]=min(ans[i-1][j]+0,ans[i-1][j-1]+{ j ~ j 的点到i距离和},ans[i-1][j-2]+{ j-1 ~ j 的点到i距离和}...,ans[i-1][j-c[i]]+{ j-c[i]+1 ~ j 的点到i的距离和})

再看ans[i][j-1]=min(ans[i-1][j-1]+0,ans[i-1][j-2]+{ j-1 ~ j-1 的点到i距离和},...,ans[i-1][j-c[i]-1]+{ j-c[i] ~ j-1 的点到i距离和})

仔细看很像取一个"滑动窗口"中最小值，但形式不可以加速，还是太慢。

因此变形一下：

ans[i][j]=min(ans[i-1][j]+0,ans[i-1][j-1] + 1到j的点到i距离和 - 1到(j-1)的点到i距离和,ans[i-1][j-2] + 1到j的点到i距离和 - 1到(j-2)的点到i距离和,...,ans[i-1][j-c[i]] + 1到j的点到i距离和 - 1到(j-c[i])的点到i距离和)
ans[i][j-1]=min(ans[i-1][j-1]+0,ans[i-1][j-2] + 1到j-1的点到i距离和 - 1到j-2的点到i距离和,...,ans[i-1][j-c[i]-1] + 1到j-1的点到i距离和 - 1到j-c[i]-1的点到i距离和)

也就是，ans[i][j]=1到j的点到i距离和 + min{ans[i-1][j-k] - 1到j-k的点到点i距离和}(0<=k<=c[i])

ans[i][j-1]=1到j-1的点到i距离和 + min{ans[i-1][j-k-1]-1到j-k-1的点到点i距离和}(0<=k<=c[i]-1)

也就是，ans[i][j]=1到j的点到i距离和 + min(ans[i-1][j]-1到j的点到i距离和,...,ans[i-1][j-c[i]]-1到j-c[i]的点到i距离和)

ans[i][j-1]=1到j-1的点到i距离和 + min(ans[i-1][j-1]-1到j-1的地点到i距离和,...,ans[i-1][j-c[i]-1]-1到j-c[i]-1的点到i距离和)

这样就可以每次i变化时用单调队列维护min{ans[i-1][j-..]-..}。

还有，ans[i][..]只跟ans[i-1][..]有关，可以用滚动数组省空间。

 1 #include<cstdio>
 2 #include<cstring> 
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;//曾经忘开LL
 6 struct Hole
 7 {
 8     LL p,c;
 9     bool operator<(const Hole& b) const
10     {
11         return p<b.p; 
12     }
13 }h[5010];
14 LL n,m;
15 LL x[5010];
16 LL ans[2][5010];
17 //曾经写错成ans[5010][2]
18 LL q[5010],l,r,i1;
19 LL s1[5010];//表示前i个洞容纳的总老鼠数量
20 LL s2[5010];//s2[j]表示预处理出的1~j的老鼠到i距离和
21 int main()
22 {
23     LL i,j;
24     scanf("%I64d%I64d",&n,&m);
25     for(i=1;i<=n;i++)
26         scanf("%I64d",&x[i]);
27     for(i=1;i<=m;i++)
28         scanf("%I64d%I64d",&h[i].p,&h[i].c);
29     sort(x+1,x+n+1);
30     sort(h+1,h+m+1);
31     for(i=1;i<=m;i++)
32         s1[i]=s1[i-1]+h[i].c;
33     memset(ans,0x3f,sizeof(ans));
34     ans[0][0]=0;//曾经误将ans[0][..]全部置0
35     if(n>s1[m])
36     {
37         printf("-1");
38         return 0;
39     }
40     for(i=1;i<=m;i++)
41     {
42         i1^=1;
43         l=r=0;
44         for(j=1;j<=min(s1[i],n);j++)
45             s2[j]=s2[j-1]+abs(x[j]-h[i].p);
46         //q[r++]=0;
47         for(j=0;j<=min(s1[i],n);j++)//曾经误将初始当做1
48         {
49             if(r>l&&q[l]<j-h[i].c)    l++;//第j个要考虑的是j-c[i] ~ j，也就是去掉j-c[i]之前的，向单调队列中加入j
50             while(r>l&&ans[i1^1][q[r-1]]-s2[q[r-1]]>=ans[i1^1][j]-s2[j])
51                 r--;
52             q[r++]=j;
53             ans[i1][j]=ans[i1^1][q[l]]-s2[q[l]]+s2[j];
54         }
55     }
56     printf("%I64d",ans[m%2][n]);
57     return 0;
58 }

View Code

upd190422：

这题被超级加强了...加强后的题目：uoj455

稍微改一下可过此题

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 #include<queue>
 6 using namespace std;
 7 #define fi first
 8 #define se second
 9 #define mp make_pair
10 #define pb push_back
11 typedef long long ll;
12 typedef unsigned long long ull;
13 struct P
14 {
15     ll x,y;
16 };
17 bool operator<(const P &a,const P &b)
18 {
19     return a.x>b.x;
20 }
21 struct PP
22 {
23     int x,w,c;
24 }p[200011];
25 bool operator<(const PP &a,const PP &b)
26 {
27     return a.x<b.x;
28 }
29 int n,m;
30 ll ans;
31 priority_queue<P> q1,q2;
32 int main()
33 {
34     int i;P t;ll v,ts=0,t1,t2;
35     scanf("%d%d",&n,&m);
36     for(i=1;i<=n;++i)
37     {
38         scanf("%d",&p[i].x);
39         p[i].c=-1;
40     }
41     for(i=1;i<=m;++i)
42     {
43         scanf("%d%d",&p[i+n].x,&p[i+n].c);
44         ts+=p[i+n].c;
45     }
46     if(n>ts)    {puts("-1");return 0;}
47     sort(p+1,p+n+m+1);
48     for(i=1;i<=n+m;++i)
49     {
50         if(p[i].c==-1)
51         {
52             if(q2.empty())    v=1e11;
53             else
54             {
55                 t=q2.top();q2.pop();
56                 v=t.x;
57                 if(t.y!=1)    q2.push((P){t.x,t.y-1});
58             }
59             ans+=p[i].x+v;
60             q1.push((P){-2*p[i].x-v,1});
61         }
62         else
63         {
64             t1=0;
65             while(p[i].c && !q1.empty())
66             {
67                 t=q1.top();v=t.x;
68                 if(p[i].x+p[i].w+v>=0)    break;
69                 q1.pop();
70                 t2=min(ll(p[i].c),t.y);
71                 t.y-=t2;p[i].c-=t2;
72                 ans+=t2*(p[i].x+p[i].w+v);
73                 t1+=t2;
74                 q2.push((P){-2*p[i].x-v,t2});
75                 if(t.y)    q1.push(t);
76             }
77             if(t1)    q1.push((P){-p[i].x-p[i].w,t1});
78             if(p[i].c)    q2.push((P){p[i].w-p[i].x,p[i].c});
79         }
80     }
81     printf("%lld
",ans);
82     return 0;
83 }

View Code