好笑的风 level
获赞
20
粉丝
6
关注
1
看过 TA
10
中国原子能科学研究院
2020
算法工程师
IP属地:北京
暂未填写个人简介
私信
关注
我只用了暴力求解,ac30😓
又菜又懒:两种情况讨论:一种情况假设原料最多的是5个吧,计算所有原料补齐到5需要的钱,然后如果手里的钱大于或等于补齐的钱,就用二者之差除以所有原料单价,再加上5就可以了;如果手里的钱小于需要补齐的钱,可以用二分法,在最小的原料数目和最多的原料数目之间二分。这个思路a了100%
投递腾讯等公司10个岗位 >
0 点赞 评论 收藏
分享
题目描述: 一条项链长L,共有0到L-1个位置,珍珠有N个(N< L),试问如何移动才能把珍珠移动到相邻位置且移动距离最短 示例:长为1000的项链,珍珠有4颗,散落在1 4 998 995位置上 结果:最短距离为8 这道题一点思路也没有,还请大家赐教!
人的立方:受到杨超度同学思路的启发,我觉得这道题可以这样想,需要一个先验知识:X轴上有N个点,求X轴上一点使它到这N个点的距离之和最小。那么根据中位数性质,这个点一定是这组数中的中位数(该性质的简单证明可以参考https://blog.csdn.net/sm_545/article/details/78196351)。 这道题在先验知识的基础上有两个变形,首先题目要求是环,那么我们就在这N个数后面再补上N个数(其中新加的N个数分别是前N个数加环的长度L)然后我们从中截取N段,使得每段都包含了所有的数,分别对每段应用先验知识;其次题目要求移动到相邻位置,那就在先验知识的基础上减去一个常数即可。因为一旦N给定,这个常数就确定了(具体求法见下方代码) public static void main(String[] args){     Scanner sc = new Scanner(System.in);     int result = Integer.MAX_VALUE;     int L = sc.nextInt();  //项链的长度     int N = sc.nextInt();  //珍珠的个数     int[] nums = new int[2*N+1];  //存拓展后的珍珠位置编号     int m, constant = 0;     m = (N+1) / 2;     for(int i = 1; i <= N ; i++){         nums[i] = sc.nextInt();         constant += Math.abs(m - i);  //求先验知识和本题差的那个常数     }     Arrays.sort(nums, 1, N+1);  //排序前N个数     for(int i = N+1; i <=2*N; i++) {         nums[i] = nums[i - N] + L;  //拓展,补上N个数     }     for(int left = 1; left <= N; left++){  //截取N段,每段包含了所有的珍珠         int answer = 0;  //按照先验知识求的距离和         int right = left + N-1;         int i = left, j = right;         while(i <= j){             answer += nums[j--] - nums[i++];         }         result = Math.min(answer - constant, result);     }     System.out.println(result); }
投递拼多多集团-PDD等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务