双端队列 Time Limit: 1 Sec Memory Limit: 128 MB (deque.cpp/c/pas) Description Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。 Sherry手头能用的工具就是若干个双端队列。 她需要依次处理这N个数，对于每个数，Sherry能做以下两件事： 1．新建一个双端队列，并将当前数作为这个队列中的唯一的数； 2．将当前数放入已有的队列的头之前或者尾之后。 对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。 Input 第一行包含一个整数N，表示整数的个数。接下来的N行每行包含一个整数Di，其中Di表示所需处理的整数。 Output 其中只包含一行，为Sherry最少需要的双端队列数。 Sample Input 6 3 6 0 9 6 3 Sample Output 2 HINT 100%的数据中N≤200000。 题解 本题纯属一道考思维的题，其实与队列关系不大，难度介于省选和noi之间 首先我们来看，本题如果用暴力是很明显不能通过的 那我们就可以思考一下队列中数的性质 1.每个数的存放顺序一定是按照下标的先后存储的，那么在同一个数列中是不是从中间开始，向两边添加数！ 并且添加数是按照下标依次添加的，越外面就越后放，也就是说越外面的数组下标就越大！ 那么在同一个双端数列中是不是其下标一定会构成一个单谷函数，如下图 2.不过，题目中并没有说没有相同数据，甚至在样例中就出现了相同数据 那我们怎么处理呢 （1）首先，我们正在排序的cmp函数中就需要将相同的数据按下标在后处理 方便后面的判断处理（即判断单调性时） （2）然后，我们需要define两个数组来存下标， 这里我就直接用 mi（每种数的最小下标），mx（每种数的最大下标）吧 在后面的遍历中 首先用一个变量来标识单调性 flag=0向下 flag=1向上 1.判断向下的单调性 1–只要我们存储的now（上一个的下标）大于我们扫到的这种数的最大下标，我们就可以继续向下扫，根据贪心的策略，我们将此时的now改为mi[i]就好了， 2–否则那就说明我们的单调性就需要改变了 如果mi mx不同的情况就会如下图 这里的mx应该更高一点 将now改为mx，flag改为1； 2.判断向上的单调性 大致方法其实万变不离其宗 如果now<mi时直接将now改为mx 否则now改为mi（贪心，越小对后面的效果越好）flag=0 3.想到这里问题就已经很明朗了 大概步骤如下 （1） 开一个有两个元素的结构体，分别用来存该数的下标，以及该数的值
struct Node{ int num,ps; }a[maxn];int mi[maxn],mx[maxn],cnt=0;（2）将数组排序。这里需要运用到cmp
bool cmp(Node x,Node y){ if(x.num==y.num)return x.ps<y.ps; return x.num<y.num; }（3）创建数组存下标
for(int i=1;i<=n;++i) { if(i==1||a[i].num!=a[i-1].num) { mx[cnt]=a[i-1].ps; mi[++cnt]=a[i].ps; } }mx[cnt]=a[n].ps;（4）遍历判断有几个单谷 附上AC代码
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int maxn=200005; int n; struct Node{ int num,ps; }a[maxn];int mi[maxn],mx[maxn],cnt=0; bool cmp(Node x,Node y){ if(x.num==y.num)return x.ps<y.ps; return x.num<y.num; } int main() { scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&a[i].num),a[i].ps=i; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;++i) { if(i==1||a[i].num!=a[i-1].num) { mx[cnt]=a[i-1].ps; mi[++cnt]=a[i].ps; } }mx[cnt]=a[n].ps; bool flag=0;int now=1<<30,ans=1; for(int i=1;i<=cnt;++i){//这里已经不用再遍历到n， //cnt表示该输入数据中一共有几种数据 //也是mx，mi的个数 if(flag==0){ if(now>mx[i])now=mi[i]; else flag=1,now=mx[i]; }else{ if(now<mi[i])now=mx[i]; else now=mi[i],flag=0,ans++; } }printf("%d\n",ans); fclose(stdin); fclose(stdout); return 0; }随手奉上一组调试数据 样例数据过水。。 500 413 431 277 88 209 127 446 284 95 316 46 345 236 199 152 271 212 52 112 231 125 494 63 78 375 199 111 372 397 254 59 255 363 123 335 239 108 417 490 254 316 421 438 24 201 83 289 93 236 418 455 96 160 35 392 86 301 224 130 7 480 331 481 134 492 351 60 63 456 454 24 76 32 397 147 460 273 22 145 108 138 290 372 483 415 65 293 262 87 91 367 263 389 365 228 445 92 369 314 101 255 353 324 41 490 128 149 353 473 73 173 80 246 303 74 375 59 209 18 469 268 316 396 35 61 171 482 274 29 197 163 285 337 245 120 82 15 262 119 295 151 309 280 416 469 361 479 150 87 105 276 208 458 182 498 112 260 79 375 346 252 121 372 437 360 278 97 275 12 215 441 269 488 319 324 161 291 133 205 76 321 409 226 126 350 236 154 169 80 435 493 30 284 193 414 269 312 114 392 332 461 166 197 146 489 207 120 4 277 52 74 309 414 291 481 6 215 290 51 275 440 102 376 331 228 229 462 385 9 432 94 110 423 62 176 190 490 92 431 271 68 319 113 399 345 437 109 274 401 424 77 389 92 458 15 399 264 312 393 277 94 426 246 103 35 114 366 55 155 110 478 431 383 399 50 284 421 50 129 496 336 482 324 360 110 395 356 22 152 290 287 332 40 305 346 449 12 299 463 285 473 412 431 93 22 23 317 295 279 345 14 378 24 74 88 428 402 322 297 130 229 278 428 322 145 294 341 424 150 361 362 317 266 164 417 6 359 188 48 151 383 58 189 269 49 75 366 223 201 164 191 291 410 154 303 415 39 135 135 446 320 307 163 474 180 49 14 62 350 156 82 463 25 435 34 155 71 128 359 266 68 360 342 218 187 65 100 166 177 84 82 73 473 411 169 475 191 265 253 291 26 455 459 234 324 242 380 166 330 138 473 470 393 367 8 260 133 420 212 23 344 412 493 4 137 213 386 426 103 25 118 364 499 379 425 354 230 258 14 71 144 278 315 136 394 156 400 411 398 396 236 322 152 408 128 78 419 20 23 324 48 58 47 93 455 486 426 108 19 278 174 279 408 487 194 458 117 214 183 301 208 435 471 293 42 376 203 276 3 400 493 59 486 109 431 432 164 103 112 169 输出 117
