投递虾皮信息等公司10个岗位 >
0 点赞 评论 收藏
分享
投递搜狗等公司10个岗位 >
0 点赞 评论 收藏
分享
0 点赞 评论 收藏
分享
RDD2DAG:无论衣食住行,都比在学校好得多,工作了才真正实现了财务自由
0 点赞 评论 收藏
分享
投递依图科技等公司10个岗位 >
0 点赞 评论 收藏
分享
2019-08-17 22:28
中国原子能科学研究院 算法工程师 又菜又懒:两种情况讨论:一种情况假设原料最多的是5个吧,计算所有原料补齐到5需要的钱,然后如果手里的钱大于或等于补齐的钱,就用二者之差除以所有原料单价,再加上5就可以了;如果手里的钱小于需要补齐的钱,可以用二分法,在最小的原料数目和最多的原料数目之间二分。这个思路a了100%
投递腾讯等公司10个岗位 >
0 点赞 评论 收藏
分享
2019-08-11 17:18
中国原子能科学研究院 算法工程师 人的立方:受到杨超度同学思路的启发,我觉得这道题可以这样想,需要一个先验知识: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 点赞 评论 收藏
分享
阿里淘天随缘内推:第Q个和倒数第Q个每一对应位置上的数之和都为n+1(n为数字数目)
投递网易等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了: