议事大厅-【赛码网】..

题目：分堆A

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

小明得到了n个石头，他想把这些石头分成若干堆，每堆至少有一个石头。他把这些石堆排在一条直线上，他希望任意相邻两堆的石头数都不一样。小明最后的得分为石头数大于等于k的石堆数，问他最多能得多少分。

严格地，小明把n个石头分成了m堆，每堆个数依次为a1，a2，.....，am。要求满足：

1、ai≥1（1≤i≤m）

2、ai≠ai+1（1≤i＜m）

3、a1+a2+...+am＝n

小明想知道a1，a2.....，am中大于等于k的数最多能有多少个？

输入

输入两个数n, k。（1≤k≤n≤109）

输出

输出最大的得分

import java.util.Scanner;

public class Main {
	 
	 static int count;
	 static int limit;
	 static int maxs = 0;
	 static int mid[];
	
	 public static void main(String args[]){
		 Scanner sc = new Scanner(System.in);
		 count = sc.nextInt();
		 limit = sc.nextInt();
		 mid = new int[10000];
		 if(limit==count){
			 System.out.print(1);
			 return;
		 }
		 dfs(0,count);
		 System.out.print(maxs);
	 }

	private static void dfs(int i, int count_max) {
		if(count_max==0){
			int coms=0;
			for(int ss=0;ss<10000;ss++){
				if(mid[ss]>=limit)
					coms++;
			}
			if(coms>maxs)
				maxs = coms;
			return;
		}
		if(count_max<0){
			return;
		}
		for(int s=1;s<=count_max;s++){
			if(i==0||(i>=1&&s!=mid[i-1])){
				mid[i] = s;
				dfs(i+1,count_max-s);
				mid[i] = 0;
			}
		}
	}
 
}

用的深搜寻找所有可能解，我在eclipse跑出结果，但是提交运行显示RuntimeError，AC为0，求助大神帮忙看看问题所在，谢谢大家

coder_MZH5ZYDW

啥算法不会卡在k的取值那最后ac20

2017-04-07 21:12

coder_EZA9VXFM

#include <iostream>

#include <string>

using namespace std;

int main()

{

int count = 0;

int n, k;

int i;

cin >> n >> k;

if (k >= n)

{

cout << n / k;

return 0;

}

for (i = 1; n > 0;)

{

if (n <= k)

{

break;

}

count++;

if (i % 2)

{

i--;

}

else

{

i++;

}

n -= (k + i);

}

cout << count;

system("pause");

}

我也很郁闷啊 10%

2017-04-07 21:16

coder_YY94K9V7

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int tone = sc.nextInt();
			int big = sc.nextInt();
			int prv = 0;
			System.out.println(dpArr(tone, big, prv));
		}
		sc.close();
	}

	public static int dpArr(int tone, int big, int prv) {
		if (tone < big) {
			return 0;
		}
		if (tone == big) {
			if (big != prv) {
				return 1;
			} else {
				return 0;
			}
		}

		// decide the first heap
		int rs = -1;
		for (int i = 1; i <= tone; i++) {
			if (i != prv) {
				int next = dpArr(tone - i, big, i);
				//Here, fuck the bug , I am so foolish
				if (i >= big) {
					next += 1;
				}
				if (rs < next) {
					rs = next;
				}
			}
		}
		return rs;
	}

}

..可怜考试出了点bug，忘记+1了。。。然后给的例子能过。。。 AC过不了，这是改好的。。。

2017-04-07 21:37

acmcoderiS3QzkOw

9行代码搞定

public class Main {
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		long k=sc.nextLong();
		long i=n/k;
		long rest=n%k;
		for(;rest<i/2;i--){
		rest+=k;}
		System.out.print(i);}
		}

2017-04-07 21:39