[已解决]菜鸡求帮助！！枚举暴力的一道水题

hjwwwwww

题目描述
平面上有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

输出

4

说明
(1,3) (4,0) (4,2) (5,3)四个点都可以被经过
贴上我的垃圾代码

1. #include<stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int N,i,j;
   
6.         int str1[100];
   
7.         int str2[100];
   
8.         int flag;// 判断斜率是否为1和-1
   
9.         int count = 0;//计算出经过的点
   
10.        
    
11.         scanf("%d", &N);
    
12.        
    
13.         for(i = 0; i < N; i++)
    
14.         {
    
15.                 scanf("%d", &str1[i]);//输入x的值
    
16.         }
    
17.        
    
18.         for(j = 0; j < N; j++)
    
19.         {
    
20.                 scanf("%d", &str2[j]);//输入y的值
    
21.         }
    
22.        
    
23.         for(i = 0; i < N; i++)
    
24.         {
    
25.                 for(j = 0; j < N; j++)
    
26.                 {
    
27.                         flag = (str1[i+j] - str1[i])/(str2[i+j] - str2[i]);//算斜率
    
28.                         while(flag == 1 || flag == -1)
    
29.                         {
    
30.                                 count+=2;       
    
31.                         }
    
32.                 }
    
33.         }
    
34.         printf("%d", count);       
    
35.        
    
36. }

复制代码

代码我肯定写的有问题 但本人太菜太菜 不会写这个题目

最佳答案

月排行榜 / 总排行榜

前路

2019-2-8 10:15:17

以下回复为个人拙见：（诚心接受指正，不接受撕逼）
解题思路为：
利用暴力枚举列出是符合斜率的所有直线；
然后再在每条直线中枚举出所有的点；
最后进行判断输出；
知识和注意点：
1，直线公式：y=x+b；
2，x，y>0;
3，x,b都在变化，b变化时代表直线改变，x变化是代表直线上的点的变化
过程：
1，对输入格式进行分析，调试；
2，采用二维数组将测试点凸显出来用于后面的点的判断；
3，用循环for (i = 0; i < 100; i++){去枚举区域内所有符合斜率的直线
4，用循环 for (temp_x = 0; temp_x < i+1; temp_x++)去枚举每条直线的所有点
5，判断该条直线是否存在测试点
6，由于需要记录测试点存在于每条直线的情况，所以用result[i]数组来记录每条直线上存在测试点的个数
7，遍历result[i]数组，找出最多测试点的直线，用变量Slope_Result_1和Slope_Result_1记录最大值
8，计算总和输出结果

总结：
刚开始我的思路与楼主思路相同，但是后面发现这种思路是判断所有符合斜率的点，并不是判断所有符合斜率的同一直线上的点；

跳转到最佳答案楼层

前路

以下回复为个人拙见：（诚心接受指正，不接受撕逼）
解题思路为：
利用暴力枚举列出是符合斜率的所有直线；
然后再在每条直线中枚举出所有的点；
最后进行判断输出；
知识和注意点：
1，直线公式：y=x+b；
2，x，y>0;
3，x,b都在变化，b变化时代表直线改变，x变化是代表直线上的点的变化
过程：
1，对输入格式进行分析，调试；
2，采用二维数组将测试点凸显出来用于后面的点的判断；
3，用循环for (i = 0; i < 100; i++){去枚举区域内所有符合斜率的直线
4，用循环 for (temp_x = 0; temp_x < i+1; temp_x++)去枚举每条直线的所有点
5，判断该条直线是否存在测试点
6，由于需要记录测试点存在于每条直线的情况，所以用result[i]数组来记录每条直线上存在测试点的个数
7，遍历result[i]数组，找出最多测试点的直线，用变量Slope_Result_1和Slope_Result_1记录最大值
8，计算总和输出结果

总结：
刚开始我的思路与楼主思路相同，但是后面发现这种思路是判断所有符合斜率的点，并不是判断所有符合斜率的同一直线上的点；

hjwwwwww

大佬们 请看看我的代码吧 应该怎么改呢

枫还

1. #include<stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int N,i,j;
   
6.         int str1[100];
   
7.         int str2[100];
   
8.         int flag;// 判断斜率是否为1和-1
   
9.         int count = 0;//计算出经过的点
   
10.         
    
11.         scanf("%d", &N);
    
12.         
    
13.         for(i = 0; i < N; i++)
    
14.         {
    
15.                 scanf("%d", &str1[i]);//输入x的值
    
16.         }
    
17.         
    
18.         for(j = 0; j < N; j++)
    
19.         {
    
20.                 scanf("%d", &str2[j]);//输入y的值
    
21.         }
    
22.         
    
23.         for(i = 0; i < N; i++)
    
24.         {
    
25.                 for(j = 0; j < N; j++)
    
26.                 {
    
27.                                 if(str1[i+j] - str1[i] != 0) {
    
28.                         flag = (str2[i+j] - str2[i])/(str1[i+j] - str1[i]);//算斜率
    
29.                         if(flag == 1 || flag == -1)
    
30.                         {
    
31.                                 count+=2;        
    
32.                         }
    
33.                             }
    
34.                 }
    
35.         }
    
36.         printf("%d", count);        
    
37.         
    
38. }

复制代码

首先判断分母不为0，用y的差去除以x的差
为什么用while？用if啊

hjwwwwww

枫还 发表于 2019-2-8 12:31
首先判断分母不为0，用y的差去除以x的差
为什么用while？用if啊

嗯嗯 这个地方要if 但是改了后的代码还是wa了 只通过了这一个样例
我想了一下这题 我没有考虑到 点可能会重复的情况 大佬可以帮忙想想这个代码要怎么改吗

hjwwwwww

hjwwwwww 发表于 2019-2-8 13:04
嗯嗯 这个地方要if 但是改了后的代码还是wa了 只通过了这一个样例
我想了一下这题 我没有考虑到 点可能 ...

@BngThea

记忆的欠片

我贴出我不完善的代码。欢迎指正

记忆的欠片

代码楼下

记忆的欠片

#include <stdio.h>
int main(){       
int N, i, j, y;       
int temp = 0;       
int tem = 0;       
int result[110] = {0};       
int row[100], column[100];       
int mat[100][100] = {0};       
printf("point count:");       
scanf("%d", &N);       
for (i = 0; i < N; i++)        {               
printf("x%d:", i+1);               
scanf("%d", &row[i]);        }       
for (j = 0; j < N; j++)        {               
printf("y%d:", j+1);               
scanf("%d", &column[j]);        }       
for (i = 0; i < N; i++)        {               
mat[row[i]][column[i]] = 1;        }       
for (j = 0; j < 100; j++)        {               
for (int z = 0; z < j+1; z++)                {                       
y = (-1) * z + j;                       
if (mat[z][y])                        {                               
result[j]++;                        }                 }        }               
for (i = 0; i < sizeof(result) / sizeof(int); i++)        {                if (result[i] > temp)                {                       
temp = result[i];                }               
result[i] = 0;        }               
for (i = 100, j = 0; i >= 0; i--, j++)        {               
for (int z = i, x = 0; x < j + 1; x++, z++)                {                        y = z - i;                       
if (mat[z][y])                        {                               
result[j]++;                        }                }        }       
for (i = 0; i < (sizeof(result) / sizeof(int)); i++)        {                if (result[i] > tem)                {                       
tem = result[i];                }        }       
printf("result = %d\n", temp + tem - 1);       
return 0;
}

hjwwwwww

记忆的欠片 发表于 2019-2-8 18:45
#include
int main(){       
int N, i, j, y;       

你好 但是结果是4哦 你的代码结果是3

记忆的欠片

hjwwwwww 发表于 2019-2-9 07:23
你好 但是结果是4哦 你的代码结果是3

我试了一下，答案是4呀E:\2.png

记忆的欠片

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int N, i, j, y;
   
6.         int temp = 0;
   
7.         int tem = 0;
   
8.         int result[110] = {0};
   
9.         int row[100], column[100];
   
10.         int mat[100][100] = {0};
    
11. 
    
12.         printf("point count:");
    
13.         scanf("%d", &N);
    
14. 
    
15.         for (i = 0; i < N; i++)
    
16.         {
    
17.                 printf("x%d:", i+1);
    
18.                 scanf("%d", &row[i]);
    
19.         }
    
20. 
    
21.         for (j = 0; j < N; j++)
    
22.         {
    
23.                 printf("y%d:", j+1);
    
24.                 scanf("%d", &column[j]);
    
25.         }
    
26. 
    
27.         for (i = 0; i < N; i++)
    
28.         {
    
29.                 mat[row[i]][column[i]] = 1;
    
30.         }
    
31. 
    
32.         for (j = 0; j < 100; j++)
    
33.         {
    
34.                 for (int z = 0; z < j+1; z++)
    
35.                 {
    
36.                         y = (-1) * z + j;
    
37.                         if (mat[z][y])
    
38.                         {
    
39.                                 result[j]++;
    
40.                         }
    
41.                 }
    
42.         }
    
43.        
    
44.         for (i = 0; i < sizeof(result) / sizeof(int); i++)
    
45.         {
    
46.                 if (result[i] > temp)
    
47.                 {
    
48.                         temp = result[i];
    
49.                 }
    
50.                 result[i] = 0;
    
51.         }
    
52.        
    
53.         for (i = 100, j = 0; i >= 0; i--, j++)
    
54.         {
    
55.                 for (int z = i, x = 0; x < j + 1; x++, z++)
    
56.                 {
    
57.                         y = z - i;
    
58.                         if (mat[z][y])
    
59.                         {
    
60.                                 result[j]++;
    
61.                         }
    
62.                 }
    
63.         }
    
64. 
    
65.         for (i = 0; i < (sizeof(result) / sizeof(int)); i++)
    
66.         {
    
67.                 if (result[i] > tem)
    
68.                 {
    
69.                         tem = result[i];
    
70.                 }
    
71.         }
    
72. 
    
73.         printf("result = %d\n", temp+tem > N? temp+tem-1:temp+tem);
    
74.         return 0;
    
75. }

复制代码

记忆的欠片

做了下判断，决绝了两条直线不在区域内相交的情况

BngThea

hjwwwwww 发表于 2019-2-8 17:05
@BngThea

身边暂无生产力工具，不方便测试，感觉你的思路和题意不太一致。
要求的是找两条线，而不是所有满足斜率的点的集合

前路

1. #include<stdio.h>
   
2. int main(void){
   
3.     int N,i,j,k,temp_x,temp_y,Slope_Result;
   
4.     int Slope_Result_1 = 0;
   
5.     int Slope_Result_2 = 0;
   
6.     int x[100], y[100];
   
7.     int result[110] = {0};
   
8.     int xy[100][100] = {0};
   
9.        
   
10.     scanf("%d", &N);       //输入点的总数
    
11. /*分别输入测试点的x和y坐标*/
    
12.     for(i = 0; i < N; i++){//输入x的值
    
13.         scanf("%d", &x[i]);
    
14.     }
    
15.     for(j = 0; j < N; j++){//输入y的值
    
16.         scanf("%d", &y[j]);
    
17.     }
    
18.     for (i = 0; i < N; i++){//将输入的点显示出来
    
19.         xy[ (x[i]) ][ (y[i]) ] = 1;
    
20.     }
    
21. /*计算斜率为-1时的所有直线上 存在输入点情况*/
    
22.     for (i = 0; i < 100; i++){
    
23.         for (temp_x = 0; temp_x < i+1; temp_x++){
    
24.             temp_y = (-1) * temp_x + i;
    
25.             if (xy[temp_x][temp_y]){
    
26.                 result[i]++;
    
27.             }
    
28.         }
    
29.     }
    
30. /*计算出斜率为-1时直线上最多点的个数*/
    
31.     for (i = 0; i < ( sizeof(result)/sizeof(int) ) ; i++){
    
32.         if (result[i] > Slope_Result_1){
    
33.             Slope_Result_1 = result[i];
    
34.             }
    
35.         result[i] = 0;
    
36.     }
    
37. /*计算斜率为1时的所有直线上 存在输入点情况*/
    
38.     for (i = 100, j = 0 ; i >=0; i--, j++){
    
39.         for (temp_x = i, k = 0 ; k < j + 1; temp_x++, k++){
    
40.             temp_y = temp_x - i;
    
41.             if (xy[temp_x][temp_y]){
    
42.                 result[i]++;
    
43.             }
    
44.         }
    
45.     }
    
46. /*计算斜率为1时直线上最多点的个数*/
    
47.     for (i = 0; i < ( sizeof(result)/sizeof(int) ) ; i++){
    
48.         if (result[i] > Slope_Result_1){
    
49.             Slope_Result_2 = result[i];
    
50.             }
    
51.         result[i] = 0;
    
52.     }
    
53. /*计算满足条件的点的总和*/
    
54.     Slope_Result = Slope_Result_1 + Slope_Result_2;
    
55.         printf("%d\n", Slope_Result > N ? Slope_Result-1 : Slope_Result);
    
56.     return 0;
    
57. }

复制代码

感谢 12#楼鱼油 提供的思路
具体回复如下

hjwwwwww

前路 发表于 2019-2-19 23:52
感谢 12#楼鱼油 提供的思路
具体回复如下

原题链接：https://ac.nowcoder.com/acm/problem/18951
大佬可以再看一下吗？好像还是不对...但是悬赏先感恩啦

前路

hjwwwwww 发表于 2019-2-20 12:46
原题链接：https://ac.nowcoder.com/acm/problem/18951
大佬可以再看一下吗？好像还是不对...但是悬赏先 ...

好的我马上去测试一下！
不过牛客网的编程题大多考虑必须全面，我以前也用，不过强迫症的我最后还是选择了搁置！