题目传送门

题意:一个长度L的管子,起点在0。n次操作,0 p表示在p的位置放上蛋糕,1表示去吃掉最近的蛋糕(如果左右都有蛋糕且距离相同,那么吃同方向的蛋糕),问最终走了多少路程

分析:用multiset来保存蛋糕的位置,以当前的位置进行二分查找相邻的蛋糕的位置,模拟这个过程。当然也可以用线段树单点更新维护。

收获:当结果和暴力程序跑出来的一样却WA时,想想是否遗漏了某些情况的讨论

multiset:

/************************************************
* Author :Running_Time
* Created Time :2015-8-22 9:31:50
* File Name :C.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7; int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
multiset<int> S; S.clear ();
multiset<int>::iterator it, l, r;
int n, m; scanf ("%d%d", &n, &m);
ll ans = 0; int now = 0, d = 1;      //d == 0:左 d == 1: 右
while (m--) {
int op, p; scanf ("%d", &op);
if (op == 0) {
scanf ("%d", &p); S.insert (p);
}
else {
if (S.empty ()) continue;        //没蛋糕了
it = S.lower_bound (now); r = it, l = it;
if (it == S.end ()) {          //右边没蛋糕
l--;
ans += (now - *l);
if (*l < now) d = 0;     //当蛋糕在左边时才改变方向,下面类似
now = *l;
S.erase (l);
}
else if (it == S.begin ()) {      //左边没蛋糕
ans += (*r - now);
if (now < *r) d = 1;
now = *r;
S.erase (r);
}
else {                  //左右都有蛋糕
l--;
int dt0 = now - *l, dt1 = *r - now;
if (dt0 == dt1) {            //左右距离相等
if (d == 0) {
ans += dt0; now = *l;
S.erase (l);
}
else {
ans += dt1; now = *r;
S.erase (r);
}
}
else if (dt0 < dt1) {        //吃左边的蛋糕
ans += dt0; now = *l;
if (dt0) d = 0;
S.erase (l);
}
else {                //吃右边的蛋糕
ans += dt1; now = *r;
if (dt1) d = 1;
S.erase (r);
}
}
}
} printf ("Case %d: %I64d\n", ++cas, ans);
} return 0;
}

Segment_Tree:

#include <bits/stdc++.h>
using namespace std; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
typedef long long ll;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct Segment_Tree {
struct Node {
int mx, mn, cnt;
}node[N<<2];
void push_up(int o) {
node[o].mx = max (node[o<<1].mx, node[o<<1|1].mx);
node[o].mn = min (node[o<<1].mn, node[o<<1|1].mn);
}
void build(int l, int r, int o) {
if (l == r) {
node[o].mx = -INF; node[o].mn = INF;
node[o].cnt = 0; return ;
}
int mid = l + r >> 1;
build (lson); build (rson);
push_up (o);
}
void updata(int p, int c, int l, int r, int o) {
if (l == r && p == l) {
node[o].mx = node[o].mn = p;
node[o].cnt += c;
if (!node[o].cnt) {
node[o].mx = -INF; node[o].mn = INF;
}
return ;
}
int mid = l + r >> 1;
if (p <= mid) updata (p, c, lson);
else updata (p, c, rson);
push_up (o);
}
int query_left(int ql, int qr, int l, int r, int o) {
if (ql <= l && r <= qr) {
return node[o].mx;
}
int mid = l + r >> 1, ret = -INF;
if (ql <= mid) ret = max (ret, query_left (ql, qr, lson));
if (qr > mid) ret = max (ret, query_left (ql, qr, rson));
return ret;
}
int query_right(int ql, int qr, int l, int r, int o) {
if (ql <= l && r <= qr) {
return node[o].mn;
}
int mid = l + r >> 1, ret = INF;
if (ql <= mid) ret = min (ret, query_right (ql, qr, lson));
if (qr > mid) ret = min (ret, query_right (ql, qr, rson));
return ret;
}
}st; int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
int n, m; scanf ("%d%d", &n, &m);
n++;
st.build (1, n, 1);
ll ans = 0; int now = 1, d = 1;
while (m--) {
int op, p; scanf ("%d", &op);
if (op == 0) {
scanf ("%d", &p); p++;
st.updata (p, 1, 1, n, 1);
}
else {
int p1 = st.query_left (0, now, 1, n, 1);
int p2 = st.query_right (now, n, 1, n, 1);
if (p1 == -INF && p2 == INF) continue;
if (p2 == INF) {
ans += now - p1;
if (p1 < now) d = 0;
now = p1;
st.updata (p1, -1, 1, n, 1);
}
else if (p1 == -INF) {
ans += p2 - now;
if (p2 > now) d = 1;
now = p2;
st.updata (p2, -1, 1, n, 1);
}
else {
int dt0 = now - p1, dt1 = p2 - now;
if (dt0 == dt1) {
if (d == 0) {
ans += dt0; now = p1;
st.updata (p1, -1, 1, n, 1);
}
else {
ans += dt1; now = p2;
st.updata (p2, -1, 1, n, 1);
}
}
else if (dt0 < dt1) {
ans += dt0; now = p1;
if (dt0) d = 0;
st.updata (p1, -1, 1, n, 1);
}
else {
ans += dt1; now = p2;
if (dt1) d = 1;
st.updata (p2, -1, 1, n, 1);
}
}
}
}
printf ("Case %d: %I64d\n", ++cas, ans);
} return 0;
}

  

05-11 22:12
查看更多