CCSP第一届 第一题 选座_ccsp历年考题

题目链接

暴力过部分样例代码

#include<cstdio>
#include<algorithm>
#define MAXN 300005
using namespace std;
int n,m,k;
int s,x,l,r;
int L[MAXN],R[MAXN];
int Abs(int x)
{return (x<0)?(-x):x;}
int calc(int x,int l,int r)
{
	int xc=(k+1)/2,yc=(k+1)/2,sum=0;
	for (int i=l;i<=r;i++)
	sum+=Abs(x-xc)+Abs(i-yc);
	return sum;
}
int main()
{
	while (scanf("%d%d",&n,&k)!=EOF)
	{
		for (int i=1;i<=k;i++)
		L[i]=R[i]=(k+1)/2;
		while (n--)
		{
			scanf("%d",&m);
			s=0x3f3f3f3f;
			for (int i=1;i<=k;i++)
			{
				int temp;
				if (L[i]==R[i]&&(m&1))
				{
					temp=calc(i,(k+1)/2-(m+1)/2+1,(k+1)/2-(m+1)/2+m);
					if (temp<s)s=temp,x=i,l=(k+1)/2-(m+1)/2+1,r=(k+1)/2-(m+1)/2+m;
					else if (temp==s&&i<x)x=i,l=(k+1)/2-(m+1)/2+1,r=(k+1)/2-(m+1)/2+m;
					else if (temp==s&&i==x&&(k+1)/2-(m+1)/2+1<l)l=(k+1)/2-(m+1)/2+1,r=(k+1)/2-(m+1)/2+m;
				}
				else if (L[i]==R[i])
				{
					temp=calc(i,(k+1)/2-m/2,(k+1)/2+m/2-1);
					if (temp<s)s=temp,x=i,l=(k+1)/2-m/2,r=(k+1)/2+m/2-1;
					else if (temp==s&&i<x)x=i,l=(k+1)/2-m/2,r=(k+1)/2+m/2-1;
					else if (temp==s&&i==x&&(k+1)/2-m/2<l)l=(k+1)/2-m/2,r=(k+1)/2+m/2-1;
				}
				if (L[i]>=m)
				{
					temp=calc(i,L[i]-m+1,L[i]);
					if (temp<s)s=temp,x=i,l=L[i]-m+1,r=L[i];
					else if (temp==s&&i<x)x=i,l=L[i]-m+1,r=L[i];
					else if (temp==s&&i==x&&L[i]-m+1<l)l=L[i]-m+1,r=L[i];
				}
				if (R[i]+m-1<=k)
				{
					temp=calc(i,R[i],R[i]+m-1);
					if (temp<s)s=temp,x=i,l=R[i],r=R[i]+m-1;
					else if (temp==s&&i<x)x=i,l=R[i],r=R[i]+m-1;
					else if (temp==s&&i==x&&R[i]<l)l=R[i],r=R[i]+m-1;
				}
			}
			if (s==0x3f3f3f3f){puts("-1");continue;}
			L[x]=min(L[x],l-1);R[x]=max(R[x],r+1);
			printf("%d %d %d\n",x,l,r);
		}
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

标程

#include <bits/stdc++.h>
#define clr(a) memset(a, 0, sizeof(a))
#define mkp make_pair
#define fir first
#define sec second
#define ll long long
using namespace std;

const int MaxN = 300010, MaxT = 1 << 20;
const ll vinf = 1ll << 60, inf = 1 << 30;
int sl[MaxN], sr[MaxN];
int n, k, m[MaxN], center;

int iabs(int x) { return x < 0 ? -x : x; }

class Segment_tree {
public:
	int maxr;
	int node[MaxN];
	pair <int, int> c[MaxT];

	void build(int l, int r, int now) {
		c[now] = mkp(inf, 0);
		if (l == r) {
			node[l] = now;
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, now << 1);
		build(mid + 1, r, now << 1 | 1);
	}
	
	void init(int r) {
		maxr = r;
		build(1, r, 1);
	}

	int x;
	pair <int, int> query(int l, int r, int now) {
		if (x < l) return mkp(inf, 0);
		if (r <= x) return c[now];
		int mid = (l + r) >> 1;
		return min(query(l, mid, now << 1), query(mid + 1, r, now << 1 | 1));
	}

	int query(int r) {
		x = r;
		pair <int, int> tmp = query(1, maxr, 1);
		//printf("query %d %d %d\n", r, tmp.fir, tmp.sec);
		return tmp.sec;
	}

	void modify(int x, int f, int s) {
		c[node[x]] = mkp(f, s);
		for (int i = node[x] >> 1; i; i >>= 1)
			c[i] = min(c[i << 1], c[i << 1 | 1]);
	}

}	T;

int mnr[MaxN];
set <pair<int, int> > q[MaxN];
int ept;

int query(int m) {
	int lim = center - m;
	int r = T.query(lim);
	return r;
}

void update(int now) {
	int pos = 0;
	if (q[now].size() == 0) mnr[now] = inf;
	else {
		mnr[now] = (*q[now].begin()).fir;
		pos = (*q[now].begin()).sec;
	}
//	printf("update %d %d %d\n", now, mnr[now] + now, pos);
	T.modify(now, now + mnr[now], pos);
}

ll calc_0(int r, int s, int l) {
	return 1ll * iabs(center - r) * l + 1ll * (s + s + l - 1) * l / 2;
}
ll calc_1(int r, int l) {
	return calc_0(r, 0, (l + 1) >> 1) + calc_0(r, 1, l >> 1);
}

pair <int, int> mpair(int r) {
	return mkp(iabs(center - r), r);
}

void Main() {
	clr(sl);
	clr(sr);
	for (int i = 1; i <= k; ++i) mnr[i] = inf;
	center = (k + 1) >> 1;
	for (int i = 1; i <= k; ++i) q[i].clear();
	T.init(center);
	ept = 0;

	for (int i = 1; i <= n; ++i) {
		int m, row, cl, cr;
		scanf("%d", &m);
		int r0 = query(m), r1;
		if (ept & 1) r1 = center - ((ept + 1) >> 1);
		else r1 = center + ((ept + 1) >> 1);

		ll val0 = calc_0(r0, min(sl[r0], sr[r0]), m), val1 = calc_1(r1, m);
		if (r1 <= 0 || r1 > k) val1 = vinf;
		if (r0 <= 0 || r0 > k) val0 = vinf;
		if ((val1 == vinf && val0 == vinf) || m > k) {
			printf("-1\n");
			continue;
		}

		if (val0 < val1 || (val0 == val1 && r0 < r1)) {
			int tmp = min(sl[r0], sr[r0]);
			row = r0;
			if (sl[r0] <= sr[r0]) {
				cl = center - sl[r0] - m + 1, cr = center - sl[r0];
				sl[r0] += m;
			} else {
				cl = center + sr[r0], cr = center + sr[r0] + m - 1;
				sr[r0] += m;
			}

			q[tmp].erase(mpair(r0));
			update(tmp);

			tmp = min(sl[r0], sr[r0]);
			q[tmp].insert(mpair(r0));
			update(tmp);
		} else {
			int tl = (m + 2) >> 1, tr = (m + 1) >> 1;
			row = r1;
			cl = center - tl + 1, cr = center + tr - 1;
			
			++ept;
			sl[r1] = tl, sr[r1] = tr;
			int tmp = tr;
			q[tmp].insert(mpair(r1));
			update(tmp);
		}
		printf("%d %d %d\n", row, cl, cr);
	}
}

int main() {
	while (scanf("%d%d", &n, &k) == 2) {
		Main();
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155