Untitled

mail@pastecode.io avatar
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);
            }
        }

    }
}