bzoj1071: [SCOI2007]组队

利用单调性+堆+乱搞即可

const int N = 5010;
struct Node {
	int Speed, Height, Val;
	friend bool operator <(Node A, Node B) { return A.Val < B.Val; }
} Dat[N];
priority_queue<Node> Q;
int n, A, B, C;

inline void Input() {
	scanf("%d%d%d%d", &n, &A, &B, &C);
	For(i, 1, n) scanf("%d%d", &Dat[i].Height, &Dat[i].Speed), Dat[i].Val = A * Dat[i].Height + B * Dat[i].Speed;
}

inline bool Cmp(Node A, Node B){ return A.Height > B.Height; }
inline void Solve() {
	sort(Dat + 1, Dat + 1 + n, Cmp);
	int Ans = 0;
	For(i, 1, n) {
		while(sz(Q)) Q.pop();
		int minH = Dat[i].Height, minW = Dat[i].Speed;
		For(j, 1, n) {
			if(Dat[i].Val > minH * A + minW * B + C) break;
			if(Dat[j].Val <= minH * A + minW * B + C) {
				minH = min(Dat[j].Height, minH);
			 	if(Dat[j].Speed >= minW) Q.push(Dat[j]);
			 	while(sz(Q) && (Q.top()).Val > minH * A + minW * B + C) Q.pop();
			}
			Ans = max(Ans, sz(Q));
 	 	}
   	}
   	printf("%d\n", Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1071");
	#endif
	Input();
	Solve();
	return 0;
}

 

评论

2 楼 promiser 2013-09-09  

xlaohe1 写道

这是C吗？
看不懂呀～
加上注释就好了。
说明也行啊，算法思想也可以啊

re xlaohe1
@xlaohe1

我是搞OI的，这是C++的代码；
详细的题解在这
  首先对原不等式变形得A*H+B*W<=C+A*h+B*w，如果把H和W作为变量，这个不等式表示在直线A*H+B*W=C+A*h+B*w以下的二维平面区域。再加上H>=h,W>=w的限制，实际上就是求x=h，y=w，A*H+B*W=C+A*h+B*w这三条直线围成的直角三角形区域内点的个数

  首先对所有的点按照纵坐标降序排序得到1顺序，按照A*H+B*W值降序排序得到2顺序，分别储存在数组中。枚举每个点，把这个点的横坐标作为h，纵坐标作为w，计算出此时三角形内点的个数，然后按照1顺序向下逐渐减小w，计算出新加入三角形区域内的点的个数；此时三角形的斜边也会下移，利用2顺序计算出离开三角形区域内的点的个数，从而计算出这个新的三角形区域内的点的个数。不断减小w直至最小。注意还要判断点的横坐标是否在范围内。

  其中统计时要用到单调队列的思想，排序我偷懒用了STL的priority_queue

1 楼 xlaohe1 2013-09-09  

这是C吗？
看不懂呀～
加上注释就好了。
说明也行啊，算法思想也可以啊