解題思路：這題利用了抽屜原理，即1-M之間的所有數(shù)與M+1的模都不相同。那么可以利用它將要查找所有區(qū)間分成[1,Y-1],[Y,2*Y-1],[2*Y,3*Y-1].........一直下去，直到所有的區(qū)間都被找一遍，然后就是保存最小的模即可。。。這樣就肯定要找每個(gè)區(qū)間的最小的模，實(shí)際上這里可以利用線段樹(shù)去找，只需要把這個(gè)區(qū)間內(nèi)最小的那個(gè)數(shù)找到就可以了。它肯定是模Y最小的，線段樹(shù)的工作難度不大，關(guān)鍵是要想到用抽屜原理去把整個(gè)的區(qū)間分段，再?gòu)拿恳欢卫锩嫒フ摇?/span>

注意，這里雖然利用線段樹(shù)可以解決問(wèn)題，但如果說(shuō)要查找的Y很小，那么分得的區(qū)間會(huì)很多，這樣查找效率就會(huì)低，不如直接查找，所以這里又有一個(gè)小技巧，當(dāng)Y比較小時(shí)，可以直接線性查找。。。

#include<iostream> #include<cstdio> #include<cstring> 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("\n");printf("Case %d:\n",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\n");else printf("%d\n",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\n");else printf("%d\n",time[tmp]);}}else {time[n] = ++cnt;num[cnt] = n;update(1,n);}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 3303(线段树+抽屉原理)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。