NOIP 普及 2012 第一轮 第 27 题：统计平面点的左下方点数：第 1 空

题目

完善程序

（坐标统计）输入 $n$ 个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即 $x,y$ 坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。

#include <iostream>
using namespace std;
const int SIZE =100;
int x[SIZE],y[SIZE],f[SIZE];
int n,i,j,max_f,ans;
int main()
{
	cin>>n;
	for(i=1;i<=n;i++) cin>>x[i]>>y[i];
	max_f=0;
	for(i=1;i<=n;i++)
	{
		f[i]= [  ①   ];
		for(j=1;j<=n;j++)
		{
			if(x[j]<x[i] && [   ②    ])
			[      ③      ] ;
		}
		if( [     ④       ])
		{
			max_f=f[i];
			[    ⑤    ];
		}
	}
	for(i=1;i<=n;i++) cout<<f[i]<<endl;
	cout<<ans<<endl;
	return 0;
}

①处应填（ ）

答案

0

题解

考点定位

本题（完善程序「统计左下方点数」第①空）考「计数初始化」,对应大纲 4.3.2 动态规划（难度【3】）。

程序思路：对每个点 i 统计位于其左下方（x、y 都更小）的点数 f[i]，再找 f 最大的点。

解题过程

①处每个点的计数初值：

``cpp f[i] = 0; ``

答案：0。

易错提醒

① 计数前清零是统计题的固定动作；② ② 处的双重循环比较 x[j]<x[i] && y[j]<y[i] 类条件后 f[i]++。