给定一个数组 nums，其中有 n 个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。
每次操作形如：任选一个整数 x ，将数组中所有大于等于 x 的数减去 x 。
[编程题]牛牛的消消乐
public long minimumValueAfterDispel (int[] nums) {
// write code here
Arrays.sort(nums);
long sum = 0;//记录整个数组的和
long max = 0;//记录能够减去的最大值
for(int j=0;j<nums.length;j++){
sum += nums[j];
int index1 = j;
int index2 = j;
int index3 = j;
for(int i=0;i<=j;i++){
while(index1 > 0 && nums[index1-1] >= nums[j]-nums[i]){
index1--;
}
while(index2 > i && nums[index2-1] >= nums[j]-nums[i]){
index2--;
}
while(index3 < nums.length && (long)nums[index3] < (long)nums[i]+nums[j]){
index3++;
}
/*
假设两次减去的数为a,b(a<b)总共分为三种情况
1.a=nums[j]-nums[i] b=nums[i]
2.a=nums[i] b=nums[j]-nums[i]
3.a=nums[i] b=nums[j]
分段函数的边界:
1. index1 < i < j < nums.length 其实index1大于i时不碍事 i-index1变成负数不会影响max的计算
2. i < index2 < j < nums.length
3. i < j < index3 < nums.length
对于第一种情况 index1到i之间的数只能减去a 即 nums[j]-nums[i], i到j之间的数只能减去b 即nums[i] , j到最后的数可以减去a+b 即nums[j]
对于第二种情况 i到index2之间的数只能减去a 即 nums[i], index2到j之间的数只能减去b 即nums[j]-nums[i] , j到最后的数可以减去a+b 即nums[j]
对于第三种情况 i到j之间的数只能减去a 即 nums[i], j到index3之间的数只能减去b 即nums[j], index3到最后的数可以减去a+b 即nums[j]+nums[i]
另外一个答案的版本之所以跟这个不一样是因为他给表达式化简了.......
*/
long tmp1 = (i-index1)*((long)nums[j]-nums[i]) + (j-i)*(long)nums[i] + (nums.length-j)*(long)nums[j];
long tmp2 = (index2-i)*((long)nums[i]) + (j-index2)*((long)nums[j]-nums[i]) + (nums.length-j)*(long)nums[j];
long tmp3 = (j-i)*(long)nums[i] + (index3-j)*(long)nums[j] + (nums.length-index3)*((long)nums[i]+nums[j]);
max = Math.max(max,tmp1);
max = Math.max(max,tmp2);
max = Math.max(max,tmp3);
}
}
return sum - max;
}
发表于 2020-04-13 14:00:30
回复(1)
import java.util.*; public class Solution { /** * 返回两次操作后，数组元素之和的最小值 * @param nums int整型一维数组 这你你需要操作的数组 * @return long长整型 */ public long minimumValueAfterDispel (int[] nums) { doFun(nums); doFun(nums); int sum = 0; for(int i=0;i<nums.length;i++){ sum += nums[i]; } return sum; } private void doFun(int[] nums){ int n = nums.length; Arrays.sort(nums); long max = 0; int index = 0; for(int i=index;i<n;i++){ long tempMax = nums[i] * (n-i); if(max<tempMax){ index = i; max = tempMax; } } int value = nums[index]; for(int i=index;i<n;i++){ nums[i] -= value; } } public static void main(String[] args) { Solution solution = new Solution(); int[] arr = new int[] {604, 349, 741, 143, 667, 997, 255, 653, 720, 631, 611, 574, 770, 125, 419, 292, 311, 756, 702, 816, 122, 602, 813, 551, 698, 764, 839, 531, 40, 239, 907, 841, 378, 710, 964, 34, 666, 864, 791, 166, 341, 987, 749, 700, 185, 96, 236, 471, 31, 569, 290, 398, 481, 472, 37, 496, 818, 393, 267, 528, 942, 429, 570, 52, 237, 80, 120, 236, 421, 8, 320, 901, 257, 767, 603, 903, 666, 373, 673, 561, 507, 736, 786, 401, 994, 746, 287, 874, 505, 516, 749, 514, 413, 883, 868, 865, 184, 19, 309, 912, 236, 827, 292, 452, 434, 32, 25, 972, 762, 123, 614, 767, 301, 812, 917, 967, 429, 921, 12, 855, 717, 965, 781, 377, 909, 492, 906, 265, 478, 538, 401, 203, 222, 418, 247, 982, 715, 168, 779, 681, 73, 507, 222, 274, 834, 330, 799, 324, 407, 310, 650, 909, 732, 540, 687, 128, 557, 883, 281, 392, 140, 103, 736, 302, 482, 711, 663, 776, 316, 460, 33, 785, 728, 686, 450, 981, 968, 729, 829, 587, 409, 305, 881, 192, 974, 370, 82, 262, 763, 132, 831, 390, 180, 541, 404, 758, 920, 607, 252, 614, 214, 51, 676, 802, 387, 430, 566, 978, 962, 147, 120, 489, 422, 118, 285, 783, 512, 548, 922, 547, 346, 530, 204, 433, 10, 145, 456, 606, 481, 410, 686, 23, 326, 834, 421, 611, 434, 432, 137, 926, 74, 64, 637, 282, 283, 316, 70, 957, 113, 919, 282, 414, 280, 992, 785, 815, 720, 343, 967, 304, 248, 204, 815, 952, 796, 205, 874, 638, 663, 404, 62, 690, 921, 317, 848, 856, 409, 651, 856, 953, 241, 376, 175, 103, 804, 28, 985, 395, 569, 390, 481, 639, 260, 565, 43, 959, 107, 18, 883, 577, 477, 197, 929, 632, 855, 789, 378, 51, 977, 489, 24, 487, 94, 922, 956, 498, 571, 191, 170, 157, 134, 129, 753, 812, 875, 592, 930, 458, 361, 534, 649, 890, 62, 590, 151, 437, 685, 93, 374, 97, 348, 759, 442, 336, 646, 736, 875, 462, 486, 485, 874, 964, 270, 655, 781, 450, 281, 413, 905, 637, 350, 33, 976, 785, 378, 206, 333, 607, 603, 683, 264, 513, 534, 769, 915, 256, 754, 448, 178, 808, 8, 958, 745, 745, 626, 771, 661, 825, 796, 394, 724, 38, 867, 730, 609, 212, 531, 850, 665, 27, 56, 180, 322, 11, 795, 375, 868, 319, 477, 681, 174, 962, 20, 823, 436, 499, 638, 816, 876, 45, 794, 234, 849, 634, 600, 408, 779, 955, 22, 439, 155, 679, 638, 187, 860, 560, 882, 369, 317, 186, 952, 0, 893, 90, 359, 4, 130, 515, 796, 334, 190, 501, 990, 17, 391, 935, 523, 992, 215, 977, 434, 322, 97, 349, 580, 430, 591, 79, 231, 650, 98, 464, 181, 658, 354, 198, 764, 866, 440, 795, 72, 153, 690, 520, 763, 515, 195, 39, 871, 782, 492, 184, 127, 188, 557, 494, 375, 167, 317, 921, 739, 385, 699, 355, 649, 750, 83, 849, 913, 850, 810, 317, 741, 11, 573, 674, 425, 293, 816, 548, 747, 177, 290, 75, 723, 33, 748, 797, 618, 323, 696, 920, 915, 788, 537, 510, 351, 631, 422, 187, 602, 789, 128, 629, 151, 621, 708, 683, 530, 176, 88, 986, 392, 391, 784, 32, 693, 561, 282, 27, 564, 331, 812, 798, 858, 239, 278, 970, 983, 292, 896, 882, 456, 972, 366, 14, 761, 152, 639, 443, 944, 117, 73, 929, 44, 193, 186, 915, 310, 39, 36, 935, 272, 195, 807, 561, 600, 811, 80, 607, 147, 200, 186, 649, 676, 76, 86, 283, 847, 740, 573, 671, 750, 615, 881, 609, 969, 73, 938, 968, 216, 144, 793, 827, 178, 229, 160, 737, 506, 713, 619, 509, 23, 422, 236, 73, 954, 710, 647, 740, 668, 767, 971, 940, 763, 573, 722, 997, 652, 8, 525, 762, 549, 761, 770, 440, 608, 784, 997, 696, 448, 72, 98, 889, 278, 898, 477, 216, 703, 159, 856, 957, 670, 933, 121, 339, 127, 439, 145, 525, 453, 384, 529, 695, 952, 134, 478, 12, 793, 932, 288, 829, 259, 35, 724, 842, 661, 43, 473, 87, 745, 630, 127, 585, 923, 456, 953, 665, 862, 581, 370, 78, 504, 513, 612, 749, 424, 512, 367, 953, 53, 678, 642, 975, 939, 104, 781, 259, 386, 838, 654, 43, 562, 776, 798, 494, 54, 50, 536, 950, 441, 860, 544, 886, 563, 592, 656, 459, 148, 816, 910, 208, 949, 816, 694, 189, 831, 998, 690, 826, 590, 217, 695, 522, 373, 878, 71, 75, 889, 681, 191, 817, 671, 280, 439, 677, 49, 456, 395, 747, 529, 127, 600, 400, 623, 541, 978, 14, 461, 790, 94, 957, 577, 212, 189, 928, 372, 227, 440, 424, 534, 946, 224, 801, 936, 102, 462, 860, 127, 93, 364, 747, 239, 972, 205, 416, 30, 652, 55, 770, 768, 799, 751, 476, 315, 801, 832, 624, 400, 386, 363, 988, 519, 311, 899, 241, 575, 128, 77, 881, 740, 645, 78, 97, 498, 930, 801, 607, 102, 972, 343, 584, 428, 982, 595, 634, 717, 48, 557, 936, 311, 803, 415, 55, 178, 856, 444, 992, 469, 705, 265, 646, 712, 526, 546, 479, 958, 593, 387, 622, 816, 12, 5, 915, 882, 216, 237, 372, 788, 842, 318, 676, 471, 609, 806, 905, 39, 640, 595, 931, 884, 564, 239, 988, 683, 563, 393, 284, 481, 605, 753, 373, 125, 115, 850, 94, 818, 787, 364, 151, 45, 303, 309, 129, 517, 266, 148, 261, 609, 219, 395, 51, 600, 800, 814, 355, 779, 189, 118, 617, 126, 52, 819, 62, 394, 899, 907, 347, 103, 246, 477, 957, 199, 881, 270, 844, 910, 122, 54, 385, 670, 641, 570, 383, 725, 539, 156, 143, 394, 897, 857, 202, 913, 41, 252, 214, 816, 635, 962, 290, 234, 242, 478, 101, 474, 967, 249, 176, 670, 441, 836, 353, 653, 285, 396, 16, 130, 924, 324, 876}; System.out.println(solution.minimumValueAfterDispel(arr)); } }
\
我本地测试的就是125437啊，沃日
编辑于 2020-04-09 22:51:33
回复(12)
long long minimumValueAfterDispel(vector<int> nums) {
// write code here
sort(nums.begin(), nums.end());
long long sum = 0;
for(auto i:nums){
sum += i;
}
long max_1 = 0;
long index_1 = 0;
for(int i=0;i<nums.size();i++){
long long temp = (nums.size() - i)*nums[i];
if(temp>max_1){
max_1 = temp;
index_1 = i;
}
}
long long temp = nums[index_1];
for(int i=index_1;i<nums.size();i++){
nums[i] = nums[i] - temp;
}
sort(nums.begin(), nums.end());
long long max_2 = 0;
for(int i=0;i<nums.size();i++){
long long temp_2 = (nums.size() - i)*nums[i];
max_2 = max(max_2, temp_2);
}
return sum - max_1 - max_2;
}
感觉思路完全没问题， 感觉测试用例有问题
发表于 2020-04-11 07:51:56
回复(2)
typedef long long ll;
class Solution {
public:
long long minimumValueAfterDispel(vector<int>& nums) {
// write code here
ll ans = 0;
ll sum = 0;
for(auto v : nums) sum += v;
sort(nums.begin(), nums.end());
ll n = nums.size();
vector<int> tmp(n,0);
for(int i = 0;i < n; i ++) { //a = nums[i] , b= tmp[j]
if(i == 0 || nums[i] != nums[i-1]){
int cnt = 0;
int k1 = 0,k2 = i;
while(k1 < i && k2 < n) {
if(nums[k1] < nums[k2] - nums[i]) tmp[cnt ++] = nums[k1 ++];
else tmp[cnt ++] = nums[k2++] - nums[i];
}
while(k1 < i) tmp[cnt ++] = nums[k1 ++];
while(k2 < n) tmp[cnt ++] = nums[k2++] - nums[i];
for(int j = 0; j < n; j ++) {
if(j == 0||tmp[j] != tmp[j-1]){
ans = max(ans,1LL*nums[i] * (n-i) + 1LL*tmp[j]*(n-j));
}
}
}
}
for(int i = 0;i < n; i ++) { //a = nums[j] - nums[i] > nums[i], b = nums[i]
if(i == 0 || nums[i] != nums[i-1]) {
int index = i + 1;
for(int j = i + 1;j < n; j ++) {
if(nums[j] != nums[j-1] && nums[j] - nums[i] > nums[i]) {
while(nums[index] < nums[j] - nums[i]) index ++;
ans = max(ans,(n-j)*1LL*nums[j] + (j-index)*1LL*(nums[j]-nums[i]) + (index-i)*1LL*nums[i]);
}
}
}
}
return sum - ans;
}
}; 假设 两次减去的数分别是 a,b,不难想象第二次减去的数b一定为原数组减去a以后的得到的数组中的某一个数。
a的选取情况有两种情况:
- a选取为原数组中的数字,这种情况比较简单直接遍历就好了。减去a的数组使用归并排序合并，再去选b。只考虑这个只能通过90%的case
- a+b 为原数组中的数字，a+b = nums[j]， b = nums[i], a = nums[j]-nums[i]> b, 这边唯一的一个疑问是为什么b一定是原数组中的数字，而不是原数据减去a以后得到的数字k。这个问题，我没有严格证明，需要数学大佬来好好想想。 我想的是用反证法，假设最终b为k，若存在nums[i] < k，我们可以增大a的值，然后最后选用b = nums[i], 若不存在 nums[i] < k。则考虑存在nums[i] > k,那我们可以考虑将a降低（保证a>nums[i]）,使得k = nums[i]。大概就是这么个意思。。证明不严谨，如有错误请大佬指出谢谢！
编辑于 2020-03-26 17:12:47
回复(0)
先将nums从小到大排序，设两次选择的数分别是a, b
可以假定第2次的数b一定小于第1次的a。否则第1次没有被减的那些数第2次仍然没有被减，那就和第1次就减(a+b)，第2次减a的效果是完全一样的。即 (a, b) 等价于 (a + b, a)，任何一个不符合假定的解(a, b)都有一个对应的符合假定的解(a + b, a)，故此假定可以成立。
a, b中一定有一个是nums中的一个值。否则不妨设 nums[j - 1] < b < nums[j], nums[i - 1] < a < nums[i], nums[k - 1] < a + b。这里 j <= i <= k:
如果 k - i >= i - j, 那么 b 尽量靠近nums[j - 1]， a尽量靠近nums[i]会更有利。设 min (b - nums[j - 1], nums[i] - a) = d, 则(a + d, b - d) 较 (a, b)更优。因为 a -> a+d, b -> b - d 至少多减了 (k - i) * d （nums[i] ~ nums[k - 1]，甚至可能nums[j - 1]整个也被多减掉了）, 而少减了(i - j) * d （nums[j] ~ nums[i - 1]），故是有利的。
如果k - i < i - j，则 b 应尽量靠近nums[j]， a尽量靠近nums[i - 1]会更有利。
编辑于 2020-08-10 22:00:21
回复(0)
public static long minimumValueAfterDispel(int[] nums) {
// write code here
Arrays.sort(nums);//顺序排列,当减去面积相同时取最小的h
long sum = 0;//总面积
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
// System.out.println("总面积："+sum);
Integer[] integers = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
integers[i] = nums[i];
}
List<Integer> f = Arrays.asList(integers);//方便修改数据
for (int i = 0; i < 2; i++) {//两次操作
long c = 0;//减去的面积
long e = 0;//结束该次操作之后的h
for (Integer j : f) {
long h = j;//给高赋值
long l = 0;//长
for (Integer k : f) {
if (k >= h) {
l++;
}
}
long d = h * l;
if (c < d && d <= sum) {//获取最大的减去面积并且该面积小于等于当前总面积
e = h;
c = d;
}
}
//结束该次操作之后对list进行处理
// System.out.println("第"+(i+1)+"次减去面积的高度：" + e);
for (int m = 0;m<f.size();m++) {
if (f.get(m) >= e) {//将数组中所有大于等于 x 的数减去 x
f.set(m,(int) (f.get(m) - e));
}
}
// System.out.println("第"+(i+1)+"次减去的面积：" + c);
sum = sum - c;
}
return sum;
} 
有没有大佬给看看，我看很多都是这样
发表于 2021-09-15 16:37:10
回复(0)
最容易理解的思路，直接暴力遍历所有的情况，获得两次能够减少的最大值
public long minimumValueAfterDispel (int[] nums) {
// write code here
long sum = 0;
for(int i:nums){
sum += i;
}
int[] nums2 = new int[nums.length];
for(int i=0;i<nums.length;i++){
nums2[i] = nums[i];
}
sum -= countMax(nums, nums2);
return sum;
}
public int countMax(int[] nums, int[] nums2){
Arrays.sort(nums);
int max = 0;
int n = nums.length;
for(int i=0;i<n;i++){
// 第一次减少的值
int dele1 = nums[i]*(n-i);
int n1 = nums[i];
for(int d=i;d<n;d++){
nums2[d] -= n1;
}
Arrays.sort(nums2);
for(int j=0;j<n;j++){
// 第二次减少的值
int dele2 = nums2[j]*(n-j);
if((dele1+dele2)>max){
// 获取两次能够减少的最大值
max = dele1+dele2;
}
}
// 复原为减少之前的值
for(int d=0;d<n;d++){
nums2[d] = nums[d];
}
}
return max;
}
发表于 2021-05-02 01:21:46
回复(0)
public long minimumValueAfterDispel (int[] nums) {
// write code here
nums=findPosition(nums);
nums=findPosition(nums);
int minValue=0;
for (int i = 0; i < nums.length; i++) {
minValue=minValue+nums[i];
}
System.out.println("minValue: "+minValue);
return minValue;
}
public int[] findPosition(int[] nums){
int max=0;
int value=0;
Arrays.sort(nums);
for (int i = 0; i <nums.length ; i++) {
int n=nums[i];
int reduce=n*(nums.length-i);
if (max<reduce){
max=reduce;
value=n;
}
}
for (int i = 0; i <nums.length ; i++){
if (nums[i]>=value) {
nums[i] = nums[i] - value;
}
}
return nums;
}
思路：
最后的值最小。只要求 保证每次 减掉的总和 最大。
1.先排序，减掉的总和等于：num[i] * 后面的个数。
2.更新num[] 。>=那个值 减掉 value
在进行 1.2步骤
但是用例3 跑不过 求大佬 指点
编辑于 2021-03-12 20:50:05
回复(1)
求助我n^2logn为啥会超时呢？
class Solution {
public:
/**
* 返回两次操作后，数组元素之和的最小值
* @param nums int整型vector 这你你需要操作的数组
* @return long长整型
*/
long long minimumValueAfterDispel(vector<int>& nums) {
// write code here
// write code here
long ans=0,sum=0;
int n=nums.size();
//System.out.println(n);
for(int i=0;i<n;i++)
sum+=nums[i];
ans=sum;
sort(nums.begin(),nums.end());
for(int i=n-1;i>0;i--){
if(i<n-1 && nums[i]==nums[i+1])
continue;
for(int j=i;j>=0;j--){
if(j<n-1 && nums[j]==nums[j+1])
continue;
long long add=nums[i]+nums[j];
long long sub=nums[i]-nums[j];
long long xx=nums[i],yy=nums[j];
int q=lower_bound(nums.begin(),nums.end(),add)-nums.begin();
int p=lower_bound(nums.begin(),nums.end(),sub)-nums.begin();
ans=min(ans,sum-(n-q)*add-(q-i)*xx-(i-j)*yy);
if(p<=j)
ans=min(ans,sum-(n-i)*xx-(i-j)*yy-(j-p)*sub);
else
ans=min(ans,sum-(n-i)*xx-(i-p)*sub-(p-j)*yy);
}
}
return ans;
}
long long min(long long x,long long y){
return x>y?y:x;
}
};
发表于 2020-11-23 22:52:35
回复(0)
def minimumValueAfterDispel(nums):
# write code here
a=len(nums)
b=[]
c=[]
for i in range(a):
sum=0
for j in range(a):
if nums[j]>=nums[i]:
sum+=nums[i]
b.append(sum)
c.append(nums[i])
sumb=len(b)
max=0
for i in range(sumb):
if b[i]>max:
max=b[i]
m=i
d=[]
mix=c[m]
for i in range(a):
if nums[i]>=mix:
nums[i]=nums[i]-mix
print(nums)
nums=[2,1,3]
minimumValueAfterDispel(nums)
minimumValueAfterDispel(nums)
# write code here
a=len(nums)
b=[]
c=[]
for i in range(a):
sum=0
for j in range(a):
if nums[j]>=nums[i]:
sum+=nums[i]
b.append(sum)
c.append(nums[i])
sumb=len(b)
max=0
for i in range(sumb):
if b[i]>max:
max=b[i]
m=i
d=[]
mix=c[m]
for i in range(a):
if nums[i]>=mix:
nums[i]=nums[i]-mix
print(nums)
nums=[2,1,3]
minimumValueAfterDispel(nums)
minimumValueAfterDispel(nums)
发表于 2020-11-13 16:01:04
回复(1)
long long minimumValueAfterDispel(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
long long sum = 0;
for (int i = 0; i < n; ++ i)
sum += nums[i];
long long min1 = INT_MAX;
int target = -1;
int index = -1;
for (int i = 0; i < n; ++ i) {
if (min1 > (sum - (n - i) * nums[i]) ) {
min1 = sum - (n - i) * nums[i];
index = i;
target = nums[i];
}
}
for (int i = index; i < n; ++ i) {
nums[i] -= target;
}
sort(nums.begin(), nums.end());
long long min2 = INT_MAX;
for (int i = 0; i < n; ++ i) {
min2 = min(min2, min1 - (n - i) * nums[i]);
}
return min2;
}
发表于 2020-11-07 21:05:26
回复(0)
void DispelBlock(vector<int> &numbers) {
int length = numbers.size();
// 得到从大到小的有序数组
for (int i=0; i<length; i++) {
for (int j=i+1; j<length; j++) {
if (numbers[j]>numbers[i]) {
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
}
}
// 计算小标区间[s,k]的几何面积
vector<long> square(length);
int indexOfMax = 0;
for (int l=0; l<length && numbers[l]>0; l++) {
square[l] = (l+1)*numbers[l];
}
for (int i=0; i<square.size(); i++) {
if (square[i] >= square[indexOfMax])
indexOfMax = i;
}
// 第一次消除
for (int i=0; i<length; i++) {
if (numbers[i] >= numbers[indexOfMax])
numbers[i] -= numbers[indexOfMax];
}
}
long long minimumValueAfterDispel(vector<int>& nums){
DispelBlock(nums);
DispelBlock(nums);
long long sum = 0;
for (int n : nums) sum += n;
return sum;
int length = numbers.size();
// 得到从大到小的有序数组
for (int i=0; i<length; i++) {
for (int j=i+1; j<length; j++) {
if (numbers[j]>numbers[i]) {
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
}
}
// 计算小标区间[s,k]的几何面积
vector<long> square(length);
int indexOfMax = 0;
for (int l=0; l<length && numbers[l]>0; l++) {
square[l] = (l+1)*numbers[l];
}
for (int i=0; i<square.size(); i++) {
if (square[i] >= square[indexOfMax])
indexOfMax = i;
}
// 第一次消除
for (int i=0; i<length; i++) {
if (numbers[i] >= numbers[indexOfMax])
numbers[i] -= numbers[indexOfMax];
}
}
long long minimumValueAfterDispel(vector<int>& nums){
DispelBlock(nums);
DispelBlock(nums);
long long sum = 0;
for (int n : nums) sum += n;
return sum;
}
用例是否准确无误？
发表于 2020-08-15 02:00:44
回复(0)
import java.util.*;
public class Solution {
/**
* 返回两次操作后，数组元素之和的最小值
* @param nums int整型一维数组 这你你需要操作的数组
* @return long长整型
*/
public long minimumValueAfterDispel (int[] nums) {
// write code here
long a=0;
long max; //要减去的最大值
long cur; //要减去的当前值
long count; //数组中大于等于该元素值的元素个数
long total; //当前数组的元素总和
long num; //保存取最大值时，当前数组中所选取的元素
for(int k=0;k<2;k++){ //操作两次
Arrays.sort(nums);
max = 0;
cur =0;
count =0;
total = 0;
num = 0;
for(int i =0;i<nums.length;i++){ //遍历数组
for(int j=0;j<nums.length;j++){ //再次遍历数组，统计数组中大于等于该元素值的元素个数
if(nums[j]>=nums[i]){
count++;
}
}
cur = nums[i]*count; //记录要减去的当前值
count = 0;
if(cur>max){ //比较当前值与最大值
max = cur;
num = nums[i]; //保存取最大值时，当前数组中所选取的元素
}
total += nums[i]; //当前数组的元素总和
}
a = total - max; //计算数组元素之和的最小值
for(int i =0;i<nums.length;i++){ //根据保存的num，生成第1次操作后的数组
if(nums[i]>=num){
nums[i]-= num;
}
}
}
return a;
}
} 
大家帮忙看一下哪里错了，感觉程序没什么问题
编辑于 2020-08-06 14:37:12
回复(2)
import java.util.*;
public class Solution {
/**
* 返回两次操作后，数组元素之和的最小值
* @param nums int整型一维数组 这你你需要操作的数组
* @return long长整型
*/
public long minimumValueAfterDispel (int[] nums) {
// write code here
int max_1=nums[0];
int max_3;
int max_2;
int max_4;
long sums=0;
int nums_length=nums.length;
long min=Long.MAX_VALUE;
int[] nums_1=new int[nums_length];
int[] nums_2=new int[nums_length];
for (int i=1;i<nums_length;i++) {
if(max_1<nums[i]) {
max_1=nums[i];
}
}
// int max_2=(int)(max_1/2)+1;
max_2=max_1;
for (int i=1;i<=max_2;i++) {
for (int j=0;j<nums_length;j++) {
if(nums[j]>=i) {
nums_1[j]=nums[j]-i;
}else {
nums_1[j]=nums[j];
}
}
max_3=nums_1[0];
for (int k=1;k<nums_length;k++) {
if(max_3<nums_1[k]) {
max_3=nums_1[k];
}
}
//int max_4=(int)(max_3/2)+1;
max_4=max_3;
for (int m=1;m<=max_4;m++) {
sums=0;
for (int j=0;j<nums_length;j++) {
if(nums_1[j]>=m) {
nums_2[j]=nums_1[j]-m;
}else {
nums_2[j]=nums_1[j];
}
sums=sums+nums_2[j];
}
if(sums<min) {
min=sums;
}
}
}
return min;
}
}
发表于 2020-08-06 12:43:09
回复(0)
class Solution:
def minimumValueAfterDispel(self, nums):
nums, len_nums = sorted(nums), len(nums)
dec = 0
for j in range(0, len_nums):
id1, id2, id3 = j, j, j
for i in range(0, j+1):
while id1 < len_nums and nums[id1] < nums[i]+nums[j]: id1 += 1
while 0 < id2 and nums[j] - nums[i] <= nums[id2-1]: id2 -= 1
while i < id3 and nums[j] - nums[i] <= nums[id3-1]: id3 -= 1
t1 = (len_nums - i) * nums[i] + (len_nums - j + i - id2) * (nums[j]-nums[i])
t2 = (len_nums-j)*nums[j] + (len_nums-id1+j-i)*nums[i]
t3 = nums[i]*(id3 -i) + (nums[j]-nums[i])*(j-id3) + nums[j]*(len_nums-j)
dec = max([dec, t1, t2, t3])
return sum(nums)-dec
def minimumValueAfterDispel(self, nums):
nums, len_nums = sorted(nums), len(nums)
dec = 0
for j in range(0, len_nums):
id1, id2, id3 = j, j, j
for i in range(0, j+1):
while id1 < len_nums and nums[id1] < nums[i]+nums[j]: id1 += 1
while 0 < id2 and nums[j] - nums[i] <= nums[id2-1]: id2 -= 1
while i < id3 and nums[j] - nums[i] <= nums[id3-1]: id3 -= 1
t1 = (len_nums - i) * nums[i] + (len_nums - j + i - id2) * (nums[j]-nums[i])
t2 = (len_nums-j)*nums[j] + (len_nums-id1+j-i)*nums[i]
t3 = nums[i]*(id3 -i) + (nums[j]-nums[i])*(j-id3) + nums[j]*(len_nums-j)
dec = max([dec, t1, t2, t3])
return sum(nums)-dec
发表于 2020-08-05 09:06:08
回复(0)
问题信息
难度：
32条回答
250收藏
13185浏览
通过挑战的用户
查看代码-
2022-08-25 22:14:00 -
2022-08-15 20:47:04 -
2022-07-29 11:11:17
-
2022-07-14 07:03:36 -
2022-06-02 17:43:46
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
