闲话:这似乎是我第一次在 luogu 场切绿。蒟蒻对思维题不太擅长 QwQ。
前置芝士
-
动态规划 / DP
-
子集划分问题 / 可行性背包
思路
首先观察这个放书的性质。结论:对于在同一个书架上的书,只需要一个人去负责。
证明也比较简单,考虑某个人去放了这一排最远的(\(c_i\) 最大的)书,那么它一定可以顺带放路上经过的所有的书。有了这个结论,就可以推出:在第 \(x\) 个书架放书的用时是固定的,就是:\(cost_x=2\times\max_\limits{i:\ r_i =x} c_i\)。
那么这个问题转化成了:
- 有 \(m\)(\(m\) 为最大书架编号)个数字,把他划分成两组,求两组内部元素的和的最大值的最小值。
- 但是由于从一个书架移动到另一个还要花费时间,所以还有额外的代价。考虑去放书的时候移动一定是按照下标递增顺序的,同理,放完书回来也不用回头,所以下标一定单调递减。设第一组的总和为 \(s_1\),最大下标为 \(a_1\),第二组的总和为 \(s_2\),最大下标最大为 \(b_2\);则代价为 \(\max(s_1+2\times a_1,s_2+2\times a_2)\)。你需要求这个代价的最小值。
上述第一个问题,是一个经典的“子集划分”问题。直接跑可行性背包加上 std::bitset
优化即可。
对于第二个问题,比较复杂,我们继续观察性质:注意到,由于这两组的并集是全集,所以 \(a_1\) 和 \(a_2\) 一定有一个是 \(m\)。
这样,我们可以固定 \(a_2=m\),然后枚举,从 \(1\) 至 \(m-1\) 枚举 \(a_1\) 的值。接下来考虑如何做到 \(a_1=i(1\le i<m)\)。由于 \(a_1\) 表示最大下标,所以任意 \(>i\) 的下标都不能划分至第一组。
-
还是可行性背包,但是有了初始代价。
-
第一组初始代价是在书架之间走路所花费的 \(2\times a_1\);
-
令 \(sum=\sum\limits_{j=1}^m cost_j\),\(cnt=\sum\limits_{j=1}^i cost_j\),则第二组的初始代价是在书架之间走路的代价 \(2\times a_2\) 加上下标 \(>i\) 的所有书架放书的代价:\(sum-cur\);第二组的总初始代价为 \(2\times m+sum-cur\)。
这个时候再去跑可行性背包,使得两部分尽量平均即可。
Code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
inline int read(){/*快读模板 略*/};
int cost[505];
bitset<250005> used;
void solve(){for(int i=1;i<=500;i++) cost[i]=0;int n=read(),m=0;for(int i=1;i<=n;i++){int r=read(),c=read();cost[r]=max(cost[r],c);m=max(m,r);}used.reset();used.set(0);int cnt=0,sum=0,ans=3e15;for(int i=1;i<=m;i++) cost[i]*=2,sum+=cost[i];for(int i=1;i<m;i++){cnt+=cost[i];used|=(used<<cost[i]);//可行性背包int a=m*2+sum-cnt,b=i*2;//a是第二组的初始代价,b是第一组的初始代价if(cnt<a-b){ans=min(ans,a);//无法达到两个相等,直接取较大值}else{ans=min((int)(b+(cnt+a-b+1)/2+(used>>((cnt+a-b+1)/2))._Find_first()),ans);//可行性背包:寻找最接近平均值的数ans=min((int)(a+(cnt-a+b+1)/2+(used>>((cnt-a+b+1)/2))._Find_first()),ans);}}cout<<ans<<endl;
}
main(){int T=read();while(T--) solve();return 0;
}