牛客网-枚举和暴力专项训练：两条斜线

ゝ一世哀愁。 2022-02-24 03:06 61阅读 0赞

链接：[https://ac.nowcoder.com/acm/problem/18951][https_ac.nowcoder.com_acm_problem_18951]  
来源：牛客网

## 题目描述 ##

平面上有n个点,现在你需要建造两条路，一条是斜率为1,  
另一条斜率为-1  
你的任务是让这两条路经过尽可能多的点  
求最多经过几个点

## 输入描述: ##

第一行输入一个整数N表示点的个数
    第二行输入N个数表示X坐标
    第三行输入N个数表示Y坐标
    1<=N<=1000 ,0<=x[i],y[i]<=999

## 输出描述: ##

输出一个整数

示例1

## 输入 ##

复制

4
    1 4 4 5
    3 0 2 3

## 输出 ##

复制

## 说明 ##

(1,3) (4,0) (4,2) (5,3)四个点都可以被经过

考虑斜率为1的斜线y-x=k1，而斜率为2的斜线y+x=k2。

遍历一遍把k1，k2的值存在map里，如果比最大值大，直接替换掉。但是相等的时候要存在vector中。

因为两条斜线可能会聚焦在一个点上，这样的话另外两条不聚焦的斜线就比它们多一个点。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int n,k1,k2,k,x[1005],y[1005];
    int sum(int k1,int k2)
    {
    	int i,k=0;
    	for(i=1;i<=n;i++)
    	{	
    		//printf("**%d %d\n",y[i]-x[i],y[i]+x[i]);
    		if((y[i]-x[i]==k1)||(y[i]+x[i]==k2))
    		{	
    			k++;			
    		}
    	}
    	return k;
    }
    int main()
    {
    	int i,j;
    	int max1=-1,max2=-1,k=0;
    	map<int,int> m1,m2,m;
    	vector<int> v1,v2;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)scanf("%d",&x[i]);
    	for(i=1;i<=n;i++)scanf("%d",&y[i]);
    	for(i=1;i<=n;i++)
    	{
    		m1[y[i]-x[i]]++;
    		m2[y[i]+x[i]]++;
    		if(m1[y[i]-x[i]]>max1)
    		{
    			v1.clear();			
    			max1=m1[y[i]-x[i]];
    			k1=y[i]-x[i];
    			v1.push_back(k1);
    		}
    		else if(m1[y[i]-x[i]]==max1)
    		{
    			k1=y[i]-x[i];
    			v1.push_back(k1);
    		}
    		if(m2[y[i]+x[i]]>max2)
    		{
    			v2.clear();
    			max2=m2[y[i]+x[i]];
    			k2=y[i]+x[i];
    			v2.push_back(k2);
    		}
    		else if(m2[y[i]+x[i]]==max2)
    		{
    			k2=y[i]+x[i];
    			v2.push_back(k2);
    		}
    	}
    	//printf("%d %d\n",k1,k2);
    	int maxx=-1;
    	for(i=0;i<v1.size();i++)
    	{
    		for(j=0;j<v2.size();j++)
    		{
    			maxx=max(maxx,sum(v1[i],v2[j]));
    		}
    	}
    	printf("%d\n",maxx);
    }

[https_ac.nowcoder.com_acm_problem_18951]: https://ac.nowcoder.com/acm/problem/18951