给出n(n<=100)个二元组,每个(x,y) (0<=x , y <= 10000)代表一个区间,问每个区间内选取同样个数的长度为1的子区间(一个长度为1的子区间只能被选取一次),可以成功分配的最大值K与n的乘积。
分析:
对于这样的数据范围很容易想到二分最大值 ,然后建边跑网络流。
那么贪心的算法会更快,来说一下贪心算法
我们二分到一个值K时。
我们面临的初始状态时 d[ 1 -> k ][ 2->k ]...[ n->k ] (代表 区间1还有k个子区间未选取,区间2还有k个子区间未选取 ......)
那么对于时刻0那么包含这个时刻的区间按 结束时刻排序可假设为 p1 , p2 , .. pt.
那么这时候把时刻0分配给p1区间是最优选择,因为选择肯定不会比丢弃时刻0更差, 把时刻0分配各其他可行性区间pk,交换依然存在最优解。
所以这个状态存在一个最优选择,只需维护出当前所转移到的状态,做最优转移即可。
下面的代码采用了set维护当前时刻可以分配到的区间。时间复杂度为((n + max_time)*logn)所以可以适合更强的数据。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #define rep1(i,x,y) for(int i=x;i<=y;i++) #define rep(i,n) for(int i=0;i<(int)n;i++) using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 110; const int M = 10101; int n , st[N],ed[N] , maxt; struct node{ int id , ed; node(int x=0,int y=0):id(x),ed(y){} bool operator<(const node& rhs)const{ if(ed != rhs.ed) return ed < rhs.ed; return id < rhs.id; } }; int rem[N]; vector<int> fir[M]; set<node> Q; typedef set<node>::iterator set_p; int judge(int k){ if(k == 0) return 1; rep1(i,1,n) rem[i]=k; Q.clear(); rep(t , maxt){ while(!Q.empty() && ((Q.begin())->ed)<=t) { if(rem[Q.begin()->id]) return 0; Q.erase(Q.begin()); } rep(i,fir[t].size()) Q.insert(node(fir[t][i] , ed[fir[t][i]])); if(Q.empty()) continue; int p = Q.begin()->id; if(--rem[p] == 0){ Q.erase(Q.begin()); } } rep1(i,1,n) if(rem[i]) return 0; return 1; } int main() { scanf("%d",&n); maxt = 0; rep1(i,1,n){ scanf("%d %d",&st[i],&ed[i]); maxt = max(maxt , ed[i]); fir[st[i]].push_back(i); } int x = 0 , y = 10001; while(x < y){ int mid = (x+y)>>1; if(judge(mid)) x=mid+1; else y = mid; } cout<<(x-1)*n<<endl; return 0; }