// 更新:下边这种放砝码的思路是不对的,其本质是贪心,这道题应该使用动态规划 // 测试样例9,8,7,5,3正确答案是16,16,贪心得到的答案是17,15 // 放砝码的思路 import java.io.*; import java.util.Arrays; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] strs = br.readLine().split(","); int[] arr = new int[strs.length]; for(int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(strs[i]); Arrays.sort(arr); int left = 0, right = 0; // 从大到小取数 for(int i = arr.length-1; i >= 0; i--){ if(left > right) right += arr[i]; else left += arr[i]; } if(left > right) System.out.println(left+","+right); else System.out.println(right+","+left); } } // 正确做法如下: import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] strs = br.readLine().split(","); br.close(); int[] arr = new int[strs.length]; int sum = 0, vol = 0; for(int i = 0; i < arr.length; i++) sum += arr[i] = Integer.parseInt(strs[i]); vol = sum>>1; // 求解背包容量为sum/2的背包问题 int[] memo = new int[vol+1]; for(int i = 0; i < arr.length; i++) for(int j = vol; j >= arr[i]; j--) if(arr[i]+memo[j-arr[i]] > memo[j]) memo[j] = arr[i]+memo[j-arr[i]]; System.out.println((sum-memo[vol])+","+memo[vol]); } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); String s=sc.next(); String[] ss=s.split(","); int[] arrs=new int[ss.length]; int sum=0; for(int i=0;i<ss.length;i++){ arrs[i]=Integer.valueOf(ss[i]); sum+=arrs[i]; } int mid=sum/2; boolean[] dp=new boolean[mid+1]; dp[0]=true; for(int i=0;i<arrs.length;i++){ for(int j=mid;j>=0;j--){ dp[j]=dp[j]||(j-arrs[i]>=0?dp[j-arrs[i]]:false); } } int res=0; for(int i=mid;i>=0;i--){ if(dp[i]){ res=i; break; } } int y=sum-res; System.out.println(y+","+res); } }
import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ArrayList<Integer> nums = new ArrayList<Integer>() {{add(0);}}; int ans = 0,max = 0; String[] instring = sc.next().split(","); for (int i=0; i!=instring.length; i++) { int in = Integer.valueOf(instring[i]); ans += in; max = Math.max(max, in); nums.add(in); } int target = ans / 2, n = nums.size()-1; boolean[] dp = new boolean[max + 5]; dp[0] = true; for (int i=1; i<=n; i++) { int cur = nums.get(i); for (int j=target; j>=cur; j--) { dp[j] |= dp[j-cur]; } } for (int i=target; i>=0; i--) { if (dp[i] == true) { System.out.printf("%d,%d\n", Math.max(i, ans-i), Math.min(i, ans-i)); return; } } } }
public class Main{ public static void main(String[] args){ Scanner input = new Scanner(System.in); String[] str = input.nextLine().split(","); int len = str.length; int[] a = new int[len]; for(int i = 0;i<len;i++){ a[i] = Integer.valueOf(str[i]); } Arrays.sort(a); int sum = 0; for(Integer i:a){ sum+=i; } int total = 0; int index= len-1; while(total<sum-total){ total+=a[index]; index--; } System.out.println(total +","+ (sum-total)); } }
#include<iostream> #include<vector> #include<algorithm> #include<stdio.h> using namespace std; int main(){ string s; cin>>s; vector<int>data; for(int i=0;i<s.length();i+=2){ int x = s[i]-'0'; data.push_back(x); } sort(data.begin(),data.end()); int length=data.size(); int sum=0; for(int i=0;i<length;i++){ sum+=data[i]; } int ans=0; if(length==1){ cout<<data[0]<<","<<0<<endl; return 0; } else if(length==2){ cout<<data[1]<<","<<data[0]<<endl; return 0; } else{ if(data[length-1]>=sum/2){ ans = data[length-1]; } else{ int target = sum/2; int csum=data[length-1]; for(int i=0;i<length-1;i++){ csum+=data[i]; if(csum==target){ ans=sum-target; } if(csum>target){ break; } } } } cout<<ans<<","<<sum-ans<<endl; return 0; }//可真无语,这个逗号,rlgl
int main() {
vector<int> v;
string s;
cin >> s;
for(int i = 0; i < s.length(); i += 2) {
int temp = s[i] - '0';
v.push_back(temp);
}
sort(v.begin(),v.end());
if (v.size() == 1) {
cout << v[0] << "," << 0;
return 0;
}
int left = 0;
int right = v.size() - 1;
int sum1 = v[left];
int sum2 = v[right];
while(left < right) {
if(sum1 <= sum2) {
left++;
if(left < right)
sum1 += v[left];
} else {
right --;
if(left < right)
sum2 += v[right];
}
}
if(sum1 > sum2) {
cout << sum1 << "," << sum2;
} else {
cout << sum2 << "," << sum1;
}
return 0;
}