bzoj 4985 评分

Posted on | Views:

二分答案 + $dp$ .

  • 这种只有比较大小的操作的题,套路大多是二分答案 $x$ ,将大于等于 $x$ 的视作 $1$ ,其余视作 $0$ ,再考虑判断.
  • 此题二分答案后,可以设 $f(i)$ 表示要将位置 $i$ 上的数确定为 $1$ ,至少需要在前面填几个 $1$ (已确定的位置不算).
  • 那么初始时,若 $i$ 的值未确定,则 $f(i)=1$ ,若 $\geq x$ ,则为 $0$ ,若 $<x$ ,则为 $inf$ .
  • 转移时用队列,将前三个取出来,将最小的两个值加起来放在最后.因为要让最后一个为 $1$ ,则这三个中至少有两个 $1$ .
  • 只剩下一个数时,判断它是否不超过可以随便填的 $1$ 的数目即可.
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
#include<bits/stdc++.h>
const int inf=1e9;
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,m;
int d[MAXN];
int fd[MAXN];
queue<int> q;
bool check(int x)
{
	while(!q.empty())
		q.pop();
	int fcnt=0;
	for(int i=1;i<=n-m;++i)
		if(fd[i]>=x)
			++fcnt;
	for(int i=1;i<=n;++i)
	{
		if(d[i]==0)
			q.push(1);
		else if(d[i]>=x)
			q.push(0);
		else
			q.push(inf);
	}
	while(1)
	{
		int a=q.front();
		q.pop();
		if(q.empty())
			return a<=fcnt;
		int b=q.front();
		q.pop();
		int c=q.front();
		q.pop();
		q.push(min(inf,min(a+b,min(a+c,b+c))));
	}
}
int main()
{
	n=read(),m=read();
	int L=1,R=0;
	for(int i=1;i<=m;++i)
	{
		int x=read(),pos=read();
		d[pos]=x;
		R=max(R,x);
	}
	for(int i=1;i<=n-m;++i)
	{
		fd[i]=read();
		R=max(R,fd[i]);
	}
	int ans=0;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(check(mid))
			ans=mid,L=mid+1;
		else
			R=mid-1;
	}
	cout<<ans<<endl;
	return 0;
}