首页 > ACM题库 > HDU-杭电 > HDU 3418-Beautiful Dream[解题报告]HOJ
2014
03-23

HDU 3418-Beautiful Dream[解题报告]HOJ

Beautiful Dream

问题描述 :

When we were a child, we all had a beautiful dream, time flies, where is your colorful dream living in now?
Get it? If not, it doesn’t matter, today is your lucky day, our kindly angel cast some items, if you get more than m different kind of items, you will get the gift of the angel: help you achieve your childhood dream.
Now we know the number of each item, find the maximum number of people who can achieve their dreams.

输入:

There are several test cases in the input.
The first line of each case contains two integer n (0 < n <= 100) and m (0 < m <= n), indicating the items’ kind number and the least different kind number of items you need collect to achieve your dream.
The n integer follows, indicating number of each item, you can assume the range of items’ number is in 1 – 1 000 000 000.
The input terminates by end of file marker.

输出:

There are several test cases in the input.
The first line of each case contains two integer n (0 < n <= 100) and m (0 < m <= n), indicating the items’ kind number and the least different kind number of items you need collect to achieve your dream.
The n integer follows, indicating number of each item, you can assume the range of items’ number is in 1 – 1 000 000 000.
The input terminates by end of file marker.

样例输入:

2 2
3 5
3 2
2 2 2

样例输出:

3
3

//BISMILLAHIRRAHMANIRRAHIM

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:0x800000")
//#define _CRT_SECURE_NO_WARNINGS 1

#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }

#define ALL(p) p.begin(),p.end()
#define MP(x, y) make_pair(x, y)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define SZ(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define i64 long long
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >

const double EPS = 1e-9;
const int INF = 0x7f7f7f7f;

int main() {
	//READ("in.txt");
	//WRITE("out.txt");
	int n,m,i,l,a[200],t;
	i64 st,fn,md,cr,lv;
	while(cin>>n>>m) {
		for(i=0;i<n;i++) {
			scanf("%d",&a[i]);
		}
		st=0;
		fn=100000000000000000ll;
		while(st+1<fn) {
			md=(st+fn)>>1;
			cr=lv=0;
			for(i=0;i<n && lv<m;i++) {
				if(a[i]>=md) lv++;
				else if(cr+a[i]<md) cr+=a[i];
				else {
					cr=(cr+a[i])%md;
					lv++;
				}
			}
			if(lv>=m) st=md;
			else fn=md-1;
		}
		if(st<fn) {
			md=fn;
			cr=lv=0;
			for(i=0;i<n && lv<m;i++) {
				if(a[i]>=md) lv++;
				else if(cr+a[i]<md) cr+=a[i];
				else {
					cr=(cr+a[i])%md;
					lv++;
				}
			}
			if(lv>=m) st=fn;
		}
		cout<<st<<'\n';
	}
	return 0;
}

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测