问题描述及思路概述：
* 将n个纸片放入口袋中,每张纸片上写一个数
* 每次从中抽取一个,记录并且放回,抽取四次
* 问和能否为m
* 若能输出Yes,否则输出No
* 样例输入:
* n = 3
* m = 10
* k = {1, 3, 5};
* 输出:
* Yes(1+1+3+5)
* 思路:
* 1.暴力枚举,四重循环,枚举所有情况 O(n^4)
* 2.优化最后一次的查询,前三重循环枚举前三次所有抽取的情况
* 最后用二分查找bin(m-A[n] + B[n] + C[n],D) O(n^3*lgn)
* 3.基于第二种方法考虑,枚举前两次抽签的情况,记录sum[n*n];在用两重循环二分查找
* bin(m-(C[n] + D[n]),sum) O(n^2*lgn)
java代码实现如下
import java.util.Arrays;
import java.util.Scanner;
public class 抽签问题及优化 {
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();//n张纸片
int m = sc.nextInt();//所求和
int[] k = new int[n];//模拟每张纸片所代表的数
for(int i = 0; i < n; i++) {
k[i] = sc.nextInt();
}
//solve1(k, m, n);
//solve2(k, m, n);
solve(k, m, n);
}
/**
* 四个数分隔成两两一对,枚举前两次抽取结果,二分查找
* @param k
* @param m
* @param n2
*/
private static void solve(int[] k, int m, int n) {
boolean ans = false;
int[] towSum = new int[n*n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
towSum[n*i+j] = k[i] + k[j];//记录
}
}
//二分查找
Arrays.sort(towSum);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(Arrays.binarySearch(towSum, m - k[i] - k[j]) >= 0)
ans = true;
}
}
if(ans)
System.out.println("Yes");
else
System.out.println("No");
}
/**
* 枚举前三次抽取结果+二分查找
* @param k
* @param m
* @param n
*/
private static void solve2(int[] k, int m, int n) {
boolean ans = false;
Arrays.sort(k);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int l = 0; l < n; l++) {
if(Arrays.binarySearch(k, m - k[i] - k[j] - k[l]) >= 0)
ans = true;
}
}
}
if(ans)
System.out.println("Yes");
else
System.out.println("No");
}
/**
* 暴力枚举
* @param k
* @param m
* @param n
*/
private static void solve1(int[] k, int m, int n) {
boolean ans = false;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int r = 0; r < n; r++) {
for(int l = 0; l < n; l++) {
if(k[i]+k[j]+k[r]+k[l] == m)
ans = true;
}
}
}
}
if(ans)
System.out.println("Yes");
else
System.out.println("No");
}
}
网友评论