[Elite 2010 February Competition Gold 【corral】]二进制步长分解、动态内存水过~★★

【题目链接】http://ace.delos.com/ioigate
八中也有。。。但是八中现在暂时爆了。等它好了的时候，搜索USACO2010就能很容易找到。
【算法分析】
原创傻×做法。。。
首先我们容易发现，假设对于两个围栏，如果一个包括另外一个的话，那么被包的就废了。
这样搞完以后呢，我们发现一个重要性质，假设用[l,r]来表示一个围栏，那么如果按l排序的话，那么r也是递增的！
我们先把数组复制多一次。这样就可以避免圈的情况。
题目转化成，在这个长度为2*c的长栏里，找一个长度为c的部分被完全覆盖。使之用的围栏最少。
我们很容易想到每次找下一个满足Lk<=Ri，且Lk最大的围栏来搞。
直到覆盖长度超过>=c。
那么我们设Right[i]表示对于当前这个栅栏i的下一个最优栅栏k。
然后我们解决问题时就可以枚举开头，然后一直Right下去统计就可以了。
但是会超时。
于是我们把Next[k][i]定义为i这个围栏，Right了2^k次以后到达哪一个围栏。
然后我们走的时候只要跟着这个跳着走就可以了。
于是问题可以在限定时间内水过。
【时间复杂度】O(n lg n)
【空间复杂度】O(n lg n)
【其它】
重要的是。。。USACO的内存少得可怜，我也不知道它到底有多少，反正就是会爆。。。
于是我百般无奈之下：malloc申请刚好大小的数组。
终于AC~
另外我依然不怕死地对10^5的读入用了cin。。
【时间与空间情况】
> Run 1: OK [0.011 secs, 4792 KB]
> Run 2: OK [0.022 secs, 4792 KB]
> Run 3: OK [0.011 secs, 4792 KB]
> Run 4: OK [0.011 secs, 4924 KB]
> Run 5: OK [0.000 secs, 4924 KB]
> Run 6: OK [0.011 secs, 5080 KB]
> Run 7: OK [0.032 secs, 5412 KB]
> Run 8: OK [0.130 secs, 7920 KB]
> Run 9: OK [0.248 secs, 11344 KB]
> Run 10: OK [0.248 secs, 11272 KB]
> Run 11: OK [0.259 secs, 16116 KB]
> Run 12: OK [0.238 secs, 11056 KB]
> Run 13: OK [0.248 secs, 8872 KB]
【CODE】
/*
ID:jie22221
TASK:corral
LANG:C++
*/
#include #include #include #include #include using namespace std;
const int N=105555*2;
struct Node{int p,l;}q[N];
bool del[N];
int n,c,mp;
int *Right,*next[20];

void input(){
cin >> c >> n;
for (int i=1;i<=n;i++)
cin >> q[i].p >> q[i].l;
}

bool cmp(Node A,Node B){
if (A.p!=B.p) return A.p return A.l>B.l;
}

void init(){
memset(del,false,sizeof(del));
for (int i=1;i<=n;i++){
q[i+n]=q[i];
q[i+n].p+=c;
}
for (int i=1,Max=-1;i<=2*n;i++)
if (q[i].p+q[i].l<=Max) del[i]=true;
else Max=q[i].p+q[i].l;
int tot=0;
for (int i=1;i<=2*n;i++)
if (!del[i]) q[++tot]=q[i];
n=tot;
}

void makenext(){
int i,j=1,k;
for (k=1;1< mp=k;
Right=(int*)malloc(sizeof(int)*(n+1));
for (i=0;i next[i]=(int*)malloc(sizeof(int)*(n+1));
for (i=1;i<=n;i++){
while (j Right[i]=j;
}
for (i=1;i<=n;i++)
next[0][i]=Right[i];
for (k=1;1< for (i=1;i<=n;i++)
next[k][i]=next[k-1][next[k-1][i]];
}
mp=k;
}

void work(){
int ans=0x7FFFFFFF,i,j,k,tmp,done;
for (k=1;q[k].p tmp=q[k].p+c;
done=1;
for (i=k,j=mp-1;j>=0;j–){
int &t=next[j][i];
if (q[t].p+q[t].l done+=1< i=t;
}
}
done++;
ans=min(ans,done);
}
cout << ans << endl;
}

int main(){
freopen("corral.in","r",stdin);
freopen("corral.out","w",stdout);
ios::sync_with_stdio(false);
input();
sort(q+1,q+n+1,cmp);
init();
makenext();
work();
return 0;
}