hdu 3303(线段树+抽屉原理)

2019-04-13 20:58发布

站内文章 / 模拟电子
17700 0 1450
解题思路：这题利用了抽屉原理，即1-M之间的所有数与M+1的模都不相同。那么可以利用它将要查找所有区间分成[1,Y-1],[Y,2*Y-1],[2*Y,3*Y-1].........一直下去，直到所有的区间都被找一遍，然后就是保存最小的模即可。。。这样就肯定要找每个区间的最小的模，实际上这里可以利用线段树去找，只需要把这个区间内最小的那个数找到就可以了。它肯定是模Y最小的，线段树的工作难度不大，关键是要想到用抽屉原理去把整个的区间分段，再从每一段里面去找。 注意，这里虽然利用线段树可以解决问题，但如果说要查找的Y很小，那么分得的区间会很多，这样查找效率就会低，不如直接查找，所以这里又有一个小技巧，当Y比较小时，可以直接线性查找。。。
#include #include #include using namespace std; const int N = 500005; const int inf = 0x7ffffff; struct Segmemt { int l,r; int mins; }tree[N<<2]; int time[N],num[N],cnt; void build(int rt,int l,int r) { tree[rt].l = l, tree[rt].r = r; tree[rt].mins = inf; if(l == r) return; int mid = (l + r) >> 1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); } void update(int rt,int t) { if(tree[rt].l == tree[rt].r) { tree[rt].mins = t; return; } int mid = (tree[rt].l + tree[rt].r) >> 1; if(mid >= t) update(rt<<1,t); else update(rt<<1|1,t); tree[rt].mins = min(tree[rt<<1].mins,tree[rt<<1|1].mins); } int query(int rt,int l,int r) { if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].mins; int ans = inf; int mid = (tree[rt].l + tree[rt].r) >> 1; if(mid >= l) ans = min(ans,query(rt<<1,l,r)); if(mid < r) ans = min(ans,query(rt<<1|1,l,r)); return ans; } int main() { int T,n,cas = 1; char ch; while(cin >> T && T) { getchar(); memset(time,-1,sizeof(time)); cnt = 0; build(1,1,N); if(cas != 1) printf(" "); printf("Case %d: ",cas++); while(T--) { cin >> ch >> n; if(ch == 'A') { if(n < 5000) { int ans = inf,tmp; for(int i = cnt; i >= 1; i--) if(num[i] % n < ans) { ans = num[i] % n; tmp = num[i]; if(ans == 0) break; } if(ans == inf) printf("-1 "); else printf("%d ",time[tmp]); } else { int interval = N / n; int ans = inf,tmp; for(int i = 0; i <= interval; i++) { int low = i * n; int hight = (i + 1) * n - 1; if(low == 0) low = 1; if(hight > N) hight = N; int res = query(1,low,hight); if(res == inf) continue; if(res % n < ans) { ans = res % n; tmp = res; } else if(res % n == ans) { if(time[res] > time[tmp]) tmp = res; } } if(ans == inf) printf("-1 "); else printf("%d ",time[tmp]); } } else { time[n] = ++cnt; num[cnt] = n; update(1,n); } } } return 0; }

热门文章