|
0 }
21 int searchit(int len)//查找
22 {
23 int addr=lg2(len);//选择入口
24 set<int>::iterator itit;
25 for(itit=kxcs[addr].begin();itit!=kxcs[addr].end();itit++)//从入口开始遍历
26 {
27 int getcs=*itit;
28 if(kx[getcs]>=len)
29 {
30 int afterlen=kx[getcs]-len;
31 int aftercs=getcs+len;
32 kx[aftercs]=afterlen;
33 deleteit(getcs);
34 if(afterlen!=0)
35 {
36 insertit(aftercs,afterlen);
37 }
38 return getcs;
39 }
40 }
41 return 0;
42 }
43 void insertit(int insertcs,int len)//添加 起始地址与长度
44 {
45 int addr=lg2(len);
46 mem.insert(insertcs);//更新总数据
47 kx[insertcs]=len;
48 for(int i=0;i<=addr;i++)//更新分组数据
49 {
50 kxcs[i].insert(insertcs);
51 }
52 /* for(set<int>::iterator itit=mem.begin();itit!=mem.end();itit++)
53 {
54 cout<<*itit<<endl;
55 }*/
56 }
57 void deleteit(int deletecs)
58 {
59 int addr=lg2(kx[deletecs]);
60 kx[deletecs]=0;
61 mem.erase(deletecs);
62 for(int i=0;i<=addr;i++)
63 {
64 kxcs[i].erase(deletecs);
65 }
66 }
67 int m,n,sta,di,mi;
68 int main()
69 {
70 memset(kx,0,sizeof(kx));
71 kx[maxn]=maxn;
72 scanf("%d %d",&n,&m);
73 mem.insert(0);
74 mem.insert(maxn);//用于保护，以免出现段错误
75 insertit(1,n);
76 while(m--)
77 {
78 scanf("%d",&sta);
79 if(sta==1)
80 {
81 scanf("%d",&mi);
82 printf("%d\n",searchit(mi));
83 }
84 else
85 {
86 scanf("%d %d",&di,&mi);
87 int flag=false;
88 int si=di;
89 if(si>n)continue;
90 int ei=di+mi-1;
91 if(ei>n)ei=n;//限制边界
92 pr=mem.equal_range(di);//该函数可以从容器中返回第一个大于等于或大于指定数的数
93 it=pr.first;
94 it--;//往后一个即为最后一个比它小的
95 if(*it+kx[*it]-1>=ei&&*it+kx[*it]-1>=si-1)continue;//新区间直接被原先区间覆盖，那该次释放无意义
96 if(*it+kx[*it]-1>=si-1)//如果最后一个比它小的结束地址大于本次释放区间起始地址，则这两个区间将连起来，初始地址将是*it
97 {
98 si=*it;
99 deleteit(*(it++));//先删除该区间，下面重建，因为还不知道区间长度
100 }
101 else it++;
102 while(true)
103 {
104 if(*it+kx[*it]-1>ei)//遍历新的释放空间会重合的所有区间，当某区间结束地址比新区间的结束地址大时遍历结束
105 {
106 if(*it<=ei+1)//该区间与新区间相连接起来
107 {
108 ei=*it+kx[*it]-1;
109 deleteit(*it);//连接起来则全算为新区间的，把该区间删除
110 }
111 insertit(si,ei-si+1);//把新区间加进去
112 break;
113 }
114 if(*it<=ei)
115 {
116 deleteit(*(it++));//区间起始地址小于等于新区间结束地址都是要和新区间重合的
117 }
118 else it++;
119 }
120 }
121 }
122 return 0;
123 }
题目 C ：V型积木
Time Limit: 1 Sec Memory Limit: 128 MB
Description
Dr.Wu的宝宝1岁了，所以Dr.Wu准备买些积木给宝宝玩，促进孩子大脑的发育。由于宝宝太小，
所以他将高低不同的积木摆放的毫无规律（如图A）。然而Dr.Wu发现，如果从当前的积木中抽走
一部分（图B，C中虚线的即表示抽走的积木），剩下的积木能够呈现出“V”形，即积木的高度先
严格递减，然后严格递增。图B中，需要抽走三个积木，剩下的积木就可以呈现出“V”形，而图C
中仅需抽走一根积木。Dr.Wu需要你帮忙找出最少抽走多少积木，剩下的积木就能呈现出“V”型？
Input
第一行： T 表示以下有T组测试数据（1≤T ≤8）
对每组测试数据：
第一行: N表示积木的个数。 （2<N<=100），
第二行是空格隔开的N个正整数，每个正整数Hi表示第i个积木的高度（0<Hi<=10000）。
输出中，仅一个数，即最少抽走的积木数。如果怎么抽走积木都无法呈现出“V”形，则输出“No Solution”。
Output
每组测试数据，输出占一行，仅一个数，即最少抽走的积木数。如果怎么抽走积木都无法呈现出“V”形，则输出“No Solution”。
Sample Input
2
6
50 30 40 10 20 60
6
5 4 3 1 2 6
Sample Output
1
0
题解：一开始想着bfs来着，然后gg。后来学习到最长上升子序列，然后就明白了什么...遍历每一个积木，求得其左边序列的最长下降子序列以及右边最长上升子序列，和最大的就是抽掉的最少的。
如诺手机查看代码不好看请转：http://paste.ubuntu.com/24387742/
#include <bits/stdc++.h>
using namespace std;
int shumu;
int jm[1050];
int b[1050];
int wei |