Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

救救孩子把!!!一直WA,麻了

Posted by eraser_ruler at 2023-01-09 22:04:17 on Problem 3111
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int n = 0;
	static int k = 0;
	static int[][] text = null;
	static int[] ans = null;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			n = sc.nextInt();
			k = sc.nextInt();
			text= new int[n][2];
			ans = new int[k];
			for(int i = 0; i < n; i++) {
				text[i][0] = sc.nextInt();
				text[i][1] = sc.nextInt();
			}
			double left = 0;
			double right = 1.1;	//上界是1,比1大就可以
			while(right-left>=1e-6) {
				double mid = (left+right)/2;
				if(C(mid)) {
					left = mid;
				}else {
					right = mid;
				}
			}
			for(int index = 0; index < k; index++){
				System.out.printf("%d%c",ans[index]+1,index==k-1?'\n':' ');
			}
		}

	}
	public static boolean C(double mid) {
		int sum = 0;
		SZ[] value = new SZ[n];
		for(int i = 0; i < n; i++) {
			value[i] = new SZ();
			value[i].pow = text[i][0] - mid*text[i][1];
			value[i].index = i;
		}
		Arrays.sort(value);
		for(int j = 0; j < k; j++) {
			sum+=value[n-j-1].pow;
			ans[j] = value[n-j-1].index;
		}
		return sum>=0;
	}
	
}
class SZ implements Comparable{
	double pow;
	int index;
	
	public int compareTo(Object o) {
		if(this.pow>((SZ)o).pow)
			return 1;
		else if(this.pow<((SZ)o).pow)
			return -1;
		else
			return 0;
	}
	
	
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator