2020年百度之星程序设计大赛-初赛二
2020年百度之星程序设计大赛-初赛二前两题解答代码思路
Poker
Problem Description
小沃沃在玩一个有趣的游戏。
初始他有 n 块钱，每一轮他需要投入至少 m 块钱，系统会拿走其中 p% 的钱，并把剩下的钱还给他。
请问在最优情况下，小沃沃最多可以玩多少轮？
假设当前一轮小沃沃投入了 x 块钱，那么他可以收回 ⌊x*(1−p%)⌋ 块钱，其中⌊a⌋ 表示 a 取下整。 小沃沃每一轮投入的钱不能超过他现在拥有的钱。
每一轮投入的钱必须为整数。Input
第一行一个正整数 test(1≤test≤100000) 表示数据组数。
对于每组数据，一行三个整数 n,m,p(1≤n≤100000,1≤m≤1000,1≤p≤100)。
Output
对每组数据输出一行一个整数表示答案。Sample Input
2
10 2 50
10 2 100
Sample Output
9
5
这道题比较简单，第一次提交遇到超时问题，后来使用了scanf和printf解决问题。
Accept代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int test,n,m,sum;
float p;
cin>>test;
while(test--)
{
scanf("%d%d%f",&n,&m,&p);//cin和cout会超时
int r=n,nums=0;
while(r>=m)
{
nums++;
r=r-m*p*0.01;
}
printf("%d\n",nums);
}
return 0;
}
目前官方提示： 观察到小沃沃每次只会投入 m 块钱，当他手上的钱大于等于 m 时，他可以继续玩，每次会被拿走⌈m∗p%⌉ 这么多钱。那么就很好算了。
Distance
Problem Description
小沃沃所在的世界是一个二维平面。他有 nn 个朋友，第 ii 个朋友距离他的距离为 a[i]，小沃沃并不知道这些朋友具体在什么点上。
请问在最优情况下，小沃沃的朋友两两之间的欧几里得距离的和的最小值是几？
假设小沃沃的位置为 P_0 = (x_0,y_0)，第 i 个朋友的位置为 P_i = (x_i,y_i)，对于所有的 i，需要满足 dist(P_0, P_i) = a[i]，并且∑ i=1 n−1∑ j=i+1 n dist(Pi,Pj) 最小，其中 dist(X,Y)dist(X,Y) 为连接点 XX 和点 YY 的线段的长度。x_i,y_i都可以是任意实数。Input
第一行一个正整数 test(1≤test≤10) 表示数据组数。
对于每组数据，第一行一个正整数 n(1≤n≤100000)。
接下来一行 n 个整数，第 i 个整数 a[i] (1≤a[i]≤1000000000) 表示第 i 个朋友和小沃沃的距离。
Output
对每组数据输出一行一个数，表示∑ i=1 n−1∑ j=i+1 ndist(Pi,P j) 的最小值。答案需要四舍五入到整数。Sample Input
2
2
3 5
5
1 2 3 4 5
Sample Output
2
20
这道题目也好理解，写程序思路直接，只是又遇到了超时问题。
#include<bits/stdc++.h> #include<cstdlib> using namespace std; //int a[1000000005];//数组太大，会出错 int *a = new int[1000000005];//全局变量动态分配 int main() { int test,n,i,j; scanf("%d",&test); while(test--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); int sum=0; sort(a+1,a+n+1);//排序 i=1; while(i<=n-1) // for(i=1;i<=n-1;i++)//时间复杂度O(n^2)，超时 { j=i+1; for(j=i+1;j<=n;j++) { sum=sum+a[j]-a[i]; } i++; } printf("%d\n",sum); } delete a; return 0; }
这道题目出现超时问题，可能数组很大或者算法不够好，两个for循环时间复杂度较高O(n^2)，虽然本地测试的时间限时小于1000ms，但是提交还是超时了，后续需要看看其他大佬怎么做的……
目前官方提示：最优情况下，所有人必然在由小沃沃出发的在一条射线上（任意两个人的距离都最小）。我们把 a 排序以后，算距离和就比较简单了。
测试时间：
我的CSDN博客：//blog.csdn.net/Charzous/article/details/107581452
我的博客园：//www.cnblogs.com/chenzhenhong/p/13377665.html
————————————————
版权声明：本文为CSDN博主「Charzous」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：//blog.csdn.net/Charzous/article/details/107581452
