Untitled
unknown
plain_text
a year ago
3.3 kB
3
Indexable
Never
package MinimalBigSum; import java.io.FileInputStream; import java.io.PrintStream; import java.util.Scanner; public class Solution { public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("input.txt")); System.setOut(new PrintStream("output.txt")); Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for(int t=1;t<=tc;t++){ int k = sc.nextInt(); int n = sc.nextInt(); int[] a = new int[n]; for(int i=0;i<n;i++){ a[i] = sc.nextInt(); } System.out.println("#"+t+" "+solution(k,a)); } } static int solution(int k,int[] a){ int l = max(a); int r = sum(a); while (true){ int mid = (l+r)/2; int b = blocks(a,mid); if(b>k){ l = mid+1; } else if (b<k) { r = mid-1; } else return r; } } static int blocks(int[] a, int mid){ int count = 0; int sum = a[0]; for (int i = 1; i < a.length; i++) { if(sum+a[i]>mid){ count++; sum = a[i]; } else { sum+=a[i]; } } return count; } static int max(int[] a){ int max = -1; for(int i=0;i<a.length;i++){ if(a[i]>max) max=a[i]; } return max; } static int sum(int[] a){ int sum = 0; for (int i = 0; i < a.length; i++) { sum+=a[i]; } return sum; } } package PointBalance2; import java.io.FileInputStream; import java.io.PrintStream; import java.util.Scanner; public class Solution { static int[]x,m; static int n; public static void main(String[] args) throws Exception{ System.setIn(new FileInputStream("input.txt")); System.setOut(new PrintStream("output.txt")); Scanner sc = new Scanner(System.in); for(int t=1;t<=2;t++){ n = sc.nextInt(); x = new int[n]; m = new int[n]; for(int i=0;i<n;i++){ x[i] = sc.nextInt(); m[i] = sc.nextInt(); } int p = f(0,n-1); // giua x[p] va x[p+1] System.out.println(p); } } static int f(int left, int right){ if(left>right) return -1; else if(left+1==right) return left; else { int mid = (left+right)/2; double fl = 0,fr = 0; for(int i=0;i<mid;i++){ int d = x[mid] - x[i]; fl+= m[i]*0.1/(d*d); } for(int i=mid+1;i<n;i++){ int d = x[i]-x[mid]; fr+= m[i]*0.1/d*d; } fl = Double.parseDouble(String.format("%.9f", fl)); fr = Double.parseDouble(String.format("%.9f", fr)); if(fl==fr){ return mid; } if(fl>fr){ return f(mid+1,right); } else { return f(left, mid+1); } } } }