北京网站制作公司兴田德润在那里,什么是域名解析错误,可以搜索国外网站的搜索引擎,jetpack wordpress问题描述 刚拿到驾照的 KJ 总喜欢开着车到处兜风#xff0c;玩完了再把车停到阿 Q 的停车场里#xff0c;虽然 她对自己停车的水平很有信心#xff0c;但她还是不放心其他人的停车水平#xff0c;尤其是 Kelukin。于是#xff0c; 她每次都把自己的爱车停在距离其它车最远… 问题描述 刚拿到驾照的 KJ 总喜欢开着车到处兜风玩完了再把车停到阿 Q 的停车场里虽然 她对自己停车的水平很有信心但她还是不放心其他人的停车水平尤其是 Kelukin。于是 她每次都把自己的爱车停在距离其它车最远的一个车位。KJ 觉得自己这样的策略非常科 学于是她开始想在一个停车场中有一排车位从左到右编号为 1 到 n初始时全部是 空的。有若干汽车进出停车场共 m 次。对于每辆进入停车场的汽车会选择与其它车距 离最小值最大的一个车位若有多个符合条件选择最左边一个。KJ 想着想着就睡着了 在她一旁的 Kelukin 想帮她完成这个心愿但是他又非常的懒不愿意自己动手于是就把 这个问题就留给了你在 KJ 理想的阿 Q 的停车场中给你车辆进出的操作序列依次输 出每辆车的车位编号。 输入格式 第一行两个整数 n 和 m表示停车场大小和操作数 接下来 m 行每行两个整数 F 和 x F 是 1 表示编号为 x 的车进停车场 F 是 2 表示编号为 x 的车出停车场 保证操作合法即 出停车场的车一定目前仍在停车场里 停车场内的车不会超过 n 输出格式 对于所有操作 1输出一个整数表示该车车位的编号 样例输入 7 11 1 15 1 123123 1 3 1 5 2 123123 2 15 1 21 2 3 1 6 1 7 1 8 样例输出 1 7 4 2 7 4 1 3 提示 【数据范围】 对 30%的数据 n1000 m1000 对 60%的数据 n200000m2000 对 100%的数据 nm200000 车的编号小于等于 10^6 分析 考场上我这个zz想了一种堆的做法 然而实现起来有缺陷 后来听他们说这是一道蛮简单的线段树 感觉自己退役算了。。。 根据题目的要求 0号和n1位是不能视为有车的 所以这两个位置需要特判 一般情况下只要找出该区间内没有停车的最远的区间 区间长度1就是下一辆要停的车与其他车相距的最远距离 不知道自己在说什么 要维护四个量 分别是x,y,mid,p x表示在当前结点线段树所在区间最左边的车停的位置 同理y表示做右边的车所停的位置 mid表示在这个小区间[x,y]中的紧邻的两辆车的最长距离除以2后的值 p表示取得mid值是所在的紧邻的两辆车的中间位置也就是在[x,y]中的答案值 网上的代码都超级** 实在是看不懂废了洪荒之力码完代码。。。 最复杂的过程就是停车其实也很好理解 每一次在新停车的时候 都查看一下第一个节点的信息线段树的根节点记录的是整个区间的信息 每辆车都有三个可能停的位置 tree[1].p,1,n 这三个点的停车相聚最远距离分别是 tree[1].mid, tree[1].x-1(假使第一个位置没有停车) n-tree[1].y(假使最后一个位置没有停车) 从三个位置中选择一个最优的添加 update的时候分别维护就好了 tree[bh].xtree[lc].x; tree[bh].ytree[rc].y; tree[bh].mid和tree[bh].p需要从三个值中择优 tree[lc] tree[rc].mid tree[rc].y-tree[lc].x1; //两个区间之间的空位 这里写代码片
#includecstdio
#includeiostream
#includecstringusing namespace std;const int N200002;
struct node{int x,y,mid,p;
};
node tree[N4];
int n,m;
int car[1000001]; //车的位置如果你6可以加离散化啊 void update(int bh)
{int lcbh1;int rc(bh1)1;if (bh){tree[bh].xtree[lc].x;tree[bh].ytree[rc].y;tree[bh].midtree[lc].mid;tree[bh].ptree[lc].p;if (tree[rc].midtree[bh].mid){tree[bh].midtree[rc].mid; tree[bh].ptree[rc].p;}int ltree[rc].y-tree[lc].x1; //两个区间之间的空位if (ltree[bh].mid){tree[bh].midl;tree[bh].p(tree[lc].ytree[rc].x)1;} }return;
}void add(int bh,int l,int r,int wz,int z)
{if (lwzlr){if (z1){tree[bh].xl;tree[bh].yr;tree[bh].mid0; //节点上有车了,当然就没有mid和p值了 tree[bh].p0;return;}else{tree[bh].x0;tree[bh].y0;tree[bh].mid0;tree[bh].p0;return;}}int mid(lr)1;if (wzmid) add(bh1,l,mid,wz,z);if (wzmid) add((bh1)1,mid1,r,wz,z);update(bh);
}int main()
{scanf(%d%d,n,m);for (int i1;im;i){int opt,u;scanf(%d%d,opt,u);if (opt1){if (tree[1].x0) //整颗线段树的信息都集中在根节点 {car[u]1; //整个停车场都是空的 }else{int mx-1;if (tree[1].x-1mx){mxtree[1].x-1;car[u]1; //第一个车位没人停 }if (tree[1].midmx) {mxtree[1].mid;car[u]tree[1].p;}if (n-tree[1].ymx){ //最后的车位没人停 mxn-tree[1].y;car[u]n;}}printf(%d\n,car[u]);add(1,1,n,1,1); }else{add(1,1,n,car[u],-1); //出停车场 }}return 0;
}转载于:https://www.cnblogs.com/wutongtong3117/p/7673536.html
