hdu3303-白红宇

hdu3303

阅读量：5861 次

发布时间：2019-06-19

本文共 3002 字，大约阅读时间需要 10 分钟。

分析：一个最暴力的想法是把加入到集合S的数据一个个按顺序保存起来，然后每次查询的时候由后向前计算余数，如果遇到余数为0的，就直接把时间输出，否则就一直比较到最后找余数最小时间最晚的，这样查询的时间复杂度是n（当前S的元素个数）。

另一个想法就是利用x、y的数据范围，建线段树表示[1,500000]这个区间，用来更新和查询任意[a,b]区间的最小值。因为[m*y,(m + 1)y - 1]内每个数除y的余数都是唯一的，而且被除数越小余数就越小，所以我们可以查询每个小区间的最小值，再比较应该取哪个时间就可以了。查询的时间复杂度为(maxN/y)*lg(maxN)，可见y越大查询时间越短。但y很小时，就要进行很多次对线段树的查询才能得出结果，所以当y很小时，应该用暴力的方法查询。

1 #pragma warning(disable:4996)  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
           8 #define maxN 1000001 9 using namespace std; 10 int sum[maxN << 1], data[maxN]; 11 int stk[maxN], s; 12 //向上更新,rt是要更新的节点的下标 13 void pushUp(int rt){ 14 int m = rt << 1; 15 if (sum[m] != -1){ 16 sum[rt] = sum[m]; 17 } 18 else{ 19 sum[rt] = sum[m | 1]; 20 } 21 } 22 //初始化线段树 23 void initTree(int a, int b, int rt){ 24 sum[rt] = -1; 25 if (a == b){ 26 return; 27 } 28 int m = rt << 1; 29 initTree(a, (a + b) / 2, m); 30 initTree((a + b) / 2 + 1, b, m | 1); 31 } 32 //更新节点 33 void update(int tgt, int time, int a, int b, int rt){ 34 if (a == b){ 35 sum[rt] = a; 36 data[a] = time; 37 return; 38 } 39 int m = rt << 1; 40 if (tgt > (a + b) / 2){ //更新右子树 41 update(tgt, time, (a + b) / 2 + 1, b, m | 1); 42 } 43 else{ //更新左子树 44 update(tgt, time, a, (a + b) / 2, m); 45 } 46 pushUp(rt); 47 } 48 int query(int ta, int tb, int a, int b, int rt){ 49 if (ta <= a && tb >= b || sum[rt] == -1){ 50 return sum[rt]; 51 } 52 int ret = -1, m = rt << 1; 53 if (ta <= (a + b) / 2){ //查询左子树 54 ret = query(ta, tb, a, (a + b) / 2, m); 55 } 56 if (ret == -1 && tb > (a + b) / 2){ //查询右子树 57 ret = query(ta, tb, (a + b) / 2 + 1, b, m | 1); 58 } 59 return ret; 60 } 61 int query(int x){ 62 int ret = 0xfffffff, start = 1, end = x - 1,rmdRet = x; 63 do{ 64 int temp = query(start, end, 1, 1000000, 1); 65 int rmdTemp = temp % x; 66 if (temp != -1){ 67 if(rmdRet > rmdTemp){ 68 rmdRet = rmdTemp; 69 ret = temp; 70 } 71 else if (rmdRet == rmdTemp && data[ret] < data[temp]){ 72 ret = temp; 73 } 74 } 75 start = end + 1; 76 end += x; 77 }while (end < 1000000); 78 if (ret == 0xfffffff){ 79 return -1; 80 } 81 else{ 82 return data[ret]; 83 } 84 } 85 int main(){ 86 int t, x, time; 87 char op; 88 int caseNum = 1; 89 while (scanf("%d", &t), t){ 90 if (caseNum != 1){ 91 printf("\n"); 92 } 93 printf("Case %d:\n", caseNum++); 94 initTree(1, 1000000, 1); 95 s = 0; 96 time = 1; 97 for (int i = 1; i <= t; i++){ 98 scanf("%*c%c%d", &op, &x); 99 if (op == 'B'){100 update(x, time++, 1, 1000000, 1);101 stk[s++] = x;102 }103 else{104 if (x > 2500){105 printf("%d\n", query(x));106 }107 else{108 int rmd = x,ans = -1;109 bool flag = false;110 for (int i = s - 1; i >= 0; i--){111 if (stk[i] % x == 0){112 printf("%d\n", i + 1);113 flag = true;114 break;115 }116 else if(stk[i] % x < rmd){117 rmd = stk[i] % x;118 ans = i + 1;119 }120 }121 if (!flag){122 printf("%d\n", ans);123 }124 }125 }126 }127 }128 return 0;129 }

转载于:https://www.cnblogs.com/ZShogg/p/3552715.html

你可能感兴趣的文章

记录一下本应用《任您记）APP项目中点击底部导航栏四个按钮，则界面颜色跟着变化及图标字放大效果...