14 条题解

  • 25
    @ 2023-4-8 16:51:28

    思路：

    老鼠最初在坐标原点，坐标系中有若干个点，问从原点走完这些点，最短的距离是多少。

    对每个奶酪的下标进行全排列，用num保存，计算每次排列中，老鼠要走多远的距离，求最小值。

    /视频讲解/ https://cdn.console.pipacoding.com/einstein/material/6afdb5f8-3ff0-44df-afd7-3ce06f86352c30000242.mp4

    参考代码

    #include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
//计算两点距离
double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double x[15], y[15], ans = 10000000000;
int num[15];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
		num[i] = i;
	}
	//num最开始保存所有奶酪的下标，对num进行全排列，就是对每个奶酪进行全排列
	do
	{
		double sum = dis(0, 0, x[num[1]], y[num[1]]);
		for (int i = 2; i <= n; i++)
		{
			// 自定义的dis函数可以计算两个坐标之间的距离
			sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]);
		}
		//更新最大值
		ans = min(ans, sum);
		// //函数会按照字母表顺序生成现有序列的下一个较大的序列，并保存在原来的地址中。若下一个序列存在，函数将返回真，否则返回假
	} while (next_permutation(num + 1, num + n + 1));
	cout << fixed << setprecision(2) << ans;
	return 0;
}

    thanks!

    • @ 2023-8-21 10:48:01

      建议up主将头文件修改为

      #include <bits./stdc++.h>
    • @ 2023-8-22 17:00:22

      非常感谢，看完瞬间秒懂

    • @ 2023-9-17 16:16:39

      不对是

      bits/stdc++.h

    • @ 2024-1-13 17:48:58

      #include <bits/stdc++.h>

      虽然方便，但是还是适合一些较为初学的题目，如果代码内存上去了就很可能MLE，我觉得还是一个一个头文件写比较好@

    • @ 2024-2-4 12:55:27

      up是对的，用 #include <bits/stdc++.h>不行，因为这里面开了变量x1,x2,y1,y2，这些变量名与万能头的有冲突，会RE

    • @ 2024-3-31 17:15:18

      射射，小弟食用了

  • 11
    @ 2023-4-6 18:18:47
    题目大意
            老鼠最初在坐标原点，坐标系中有若干个点，问从原点走完这些点，最短的距离是多少。

    完整思路
            对每个奶酪的下标进行全排列，用num保存，计算每次排列中，老鼠要走多远的距离，求最小值。

    核心代码 
    
// num最开始保存所有奶酪的下标，对num进行全排列，就是对每个奶酪进行全排列
do
{
	double sum = dis(0, 0, x[num[1]], y[num[1]]);
	for (int i = 2; i <= n; i++)
	{ // 自定义的dis函数可以计算两个坐标之间的距离
		sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]);
	}
	ans = min(ans, sum);
} while (next_permutation(num + 1, num + n + 1));
    • 1
      @ 2024-3-30 18:45:42 
      #include <bits/stdc++.h>
using namespace std;
double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double x[15], y[15], ans = 10000000000;
int num[15];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
		num[i] = i;
	}
	do
	{
		double sum = dis(0, 0, x[num[1]], y[num[1]]);
		for (int i = 2; i <= n; i++)
		{
			sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]);
		}
		ans = min(ans, sum);
	} while (next_permutation(num + 1, num + n + 1));
	cout << fixed << setprecision(2) << ans;
	return 0;
}
      • 1
        @ 2023-7-31 23:18:11

        思路 做不出来建议看一下课程中的“夺取宝石”的讲解，参考一下练7的代码， 本题思路类似就是要多算一段： 坐标【0，0】到第一块被吃掉的奶酪的距离

        &&题中坐标可能是负的，但没关系。

        代码奉上~~~

        #include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
double x[15],y[15];
int s[15],n;
double sum,ans;
double dis(int x1,int y1,int x2,int y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
    ans=999999999.00;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        s[i]=i;
    }
    do
    {
        sum=dis(0,0,x[s[1]],y[s[1]]);
        for(int i=1;i<n;i++)
        {
            int q=s[i],w=s[i+1];
             sum+=dis(x[q],y[q],x[w],y[w]);
        }
        ans=min(sum,ans);
    }while(next_permutation(s+1,s+n+1));
    cout<<fixed<<setprecision(2)<<ans;
    return 0;
}

        注意事项： 1，保留两位小数。 2，把谁定义成小数变量谁是整数变量 3，距离函数返回的是小数变量 4，！！！不要抄袭！！！

      • 1
        @ 2023-7-28 13:44:58 
        #include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
	double x[15], y[15], ans = 10000000000;
	int num[15];
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
		num[i] = i;
	}

		do
	{
		double sum = dis(0, 0, x[num[1]], y[num[1]]);
		for (int i = 2; i <= n; i++)
		{
			sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]);
		}
		ans = min(ans, sum);
			} while (next_permutation(num + 1, num + n + 1));
	cout << fixed << setprecision(2) << ans;
	return 0;
}

        呵呵呵呵呵呵呵呵呵

        • 0
          @ 2024-3-22 20:00:42 
          #include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double x[15], y[15], ans = 10000000000;
int num[15];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
		num[i] = i;
	}
	do
	{
		double sum = dis(0, 0, x[num[1]], y[num[1]]);
		for (int i = 2; i <= n; i++)
		{
			sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]);
		}
		ans = min(ans, sum);
	} while (next_permutation(num + 1, num + n + 1));
	cout << fixed << setprecision(2) << ans;
	return 0;
}
          • 0
            @ 2024-3-4 20:48:14

            #include <iostream> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; double dis(double x1, double y1, double x2, double y2) { //计算两点间距离 return sqrt((x1-x2)(x1-x2) + (y1-y2)(y1-y2)); } double x[15], y[15], ans = 10000000000; int num[15]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i]; num[i] = i; } do { double sum = dis(0,0,x[num[1]],y[num[1]]); //计算当前排列下的总距离 for (int i=2;i<=n;i++) { sum+=dis(x[num[i-1]],y[num[i-1]],x[num[i]],y[num[i]]); }

                ans = min(ans, sum);
} while (next_permutation(num+1,num+n+1));
cout << fixed << setprecision(2) << ans;
return 0;

            }

            • 0
              @ 2024-1-6 17:41:27 
              #include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double x[15], y[15], ans = 10000000000;
int num[15];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
		num[i] = i;
	}
	do
	{
		double sum = dis(0, 0, x[num[1]], y[num[1]]);
		for (int i = 2; i <= n; i++)
		{
			sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]);
		}
		ans = min(ans, sum);
	} while (next_permutation(num + 1, num + n + 1));
	cout << fixed << setprecision(2) << ans;
	return 0;
}
              • 0
                @ 2023-8-9 20:44:23

                不知道为什么，我用普通方法超时了，所以我加了输入输出加速程序，并且因为printf不能使用，我用了<iomanip>里的cout<<fixed<<serprecision(2)<<ans<<endl;

                #include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int num[15],n;
double x[15],y[15],sum,ans=999999999;
double dis(int x1,int y1,int x2,int y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        num[i]=i;
    }
    do{
        sum=dis(0,0,x[num[1]],y[num[1]]);
        for(int i=1;i<n;i++)sum+=dis(x[num[i]],y[num[i]],x[num[i+1]],y[num[i+1]]);
        ans=min(sum,ans);
    }while(next_permutation(num+1,num+n+1));
    cout<<fixed<<setprecision(2)<<ans<<endl;
    return 0;
}
                • @ 2023-11-12 17:56:44

                  我刚开始也超时了，然后就把dis函数改了，先定义两个变量分别等于x1-x2和y1-y2，然后用这两变量替换掉公式中的，少算一次两个式子，勉强过关。还有建议楼主把dis函数的四个参数改成double类型的，因为题目说坐标是实数。

                • @ 2023-11-30 9:55:29

                  printf在cstdio头文件里 用法：printf("%.2f\n", ans);

              • -2
                @ 2023-4-7 20:56:51

                有没有同学可以解答一下为什么没有用函数来求两点之间距离会TLE但是用了就不会？

                • @ 2023-4-8 16:36:30

                  函数优化了时间呗

                • @ 2023-4-8 18:12:04

                  可以将你的代码放在这一题的讨论里面，不看代码无法解决疑问

                • @ 2024-1-13 17:56:13

                  函数只要编译一次，而且看起来更美观，但不写的话就要编译很多次，还增加代码量，不容易DEBUG

              • -3
                @ 2024-3-30 12:29:07

                吃奶酪

                学过平面直角坐标系的人都知道，两点之间坐标公式十分实用，就比如求A和B之间的距离，可以这样算：如A(x1,y1),B(x2,y2),AB=√¯(¯x¯1-¯x¯2)¯²¯+¯(y¯1¯-¯y¯2¯)¯²¯¯(没有根号，这样凑合着看吧=） 因此我们可以把两点之间距离公式的函数写出来：sqrt((x1-x2) * (x1-x2)+(y1-y2) * (y1-y2)) 然后就到了主函数，输入一堆数据之后，开始do while循环，sum先+=(0,0)到第一个数据的距离，用之前写的函数计算，然后再写个for循环，遍历一下数组，用之前写的函数计算距离并加到sum里边去。for循环一出来，和ans比较大小，小的存进ans里。while里面的判断条件一点不变，还是next_permutation()。最后，输出ans（保留两位小数），大功告成。最后的最后，最好加个return 0;。

                —————————————————————AC代码—————————————————————

                #include <bits/stdc++.h>
using namespace std;
double juli(double x1, double x2, double y1, double y2)//两点之间距离公式
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double x[15],y[15],ans =999999;
int num[15];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        num[i]=i;
    }
    do{
        double sum=juli(0,x[num[1]],0,y[num[1]]);
        for (int i=2;i<=n;i++){
            sum+=juli(x[num[i-1]],x[num[i]],y[num[i-1]],y[num[i]]);
        }
        ans=min(sum,ans);
    }while (next_permutation(num+1,num+n+1));
    printf("%.2f",ans);
    return 0;
}
                • @ 2024-5-25 21:35:28

                  本六年级笑学生表示没学过平面直角坐标系……

              • -8
                @ 2023-4-8 19:25:48 
                #include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double x[15], y[15], ans = 10000000000;
int num[15];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i];
		num[i] = i;
	}
	do
	{
		double sum = dis(0, 0, x[num[1]], y[num[1]]);
		for (int i = 2; i <= n; i++)
		{
			sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]);
		}
		ans = min(ans, sum);
	} while (next_permutation(num + 1, num + n + 1));
	cout << fixed << setprecision(2) << ans;
	return 0;
              • -12
                @ 2023-6-17 14:44:52

                #include <iostream> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; //计算两点距离 double dis(double x1, double y1, double x2, double y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } double x[15], y[15], ans = 10000000000; int num[15]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i]; num[i] = i; } //num最开始保存所有奶酪的下标，对num进行全排列，就是对每个奶酪进行全排列 do { double sum = dis(0, 0, x[num[1]], y[num[1]]); for (int i = 2; i <= n; i++) { // 自定义的dis函数可以计算两个坐标之间的距离 sum += dis(x[num[i - 1]], y[num[i - 1]], x[num[i]], y[num[i]]); } //更新最大值 ans = min(ans, sum); // //函数会按照字母表顺序生成现有序列的下一个较大的序列，并保存在原来的地址中。若下一个序列存在，函数将返回真，否则返回假 } while (next_permutation(num + 1, num + n + 1)); cout << fixed << setprecision(2) << ans; return 0; }

                • -16
                  @ 2023-6-4 15:10:29

                  不会的去课上看原题

                  • 1

                  【挑战题】吃奶酪

                  信息

                  ID
                  4
                  时间
                  1000ms
                  内存
                  256MiB
                  难度
                  4
                  标签
                  递交数
                  2293
                  已通过
                  1067
                  上传者
                  1. 关于
                  2. 联系我们
                  3. 隐私
                  4. 服务条款
                  5. 版权申诉
                  6. Language
                  7. 兼容模式
                  8. 主题
                  3. Worker 0, 30ms
                  4. Powered by Hydro v4.9.24 Community, Modified by hetao