uvalive 3971 - Assemble(二分搜索 + 贪心）

题目大意：有若干个零件，每个零件给出的信息有种类，名称，价格，质量，现在给出一个金额，要求在这个金额范围内，将每个种类零件都买一个，并且尽量让这些零件中质量最小的越大，输出质量最小的值。

解题思路：首先可以用二分搜索确定质量，然后在搜索的过程中要判断这个质量是否能被满足，判断函数可以用贪心，在每一类的零件中选择价格最低且质量大于等于当前质量的零件。（事先按照价格大小排序）。

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

const int N = 1005;

const int M = 25;

struct State {

    char name[M];

    int money;

    int wei;

}s[N][N];

int cnt, sum, son[N];

char str[N][M], sex[M];

bool cmp(const State& a, const State& b) {

    return a.money < b.money;

}

int find(char sex[]) {

    for (int i = 0; i < cnt; i++)

	if(strcmp(sex, str[i]) == 0)

	    return i;

    strcpy(str[cnt], sex);

    return cnt;

}

bool judge(int Min) {

    int tmp = 0;

    for (int i = 0; i < cnt; i++) {

	int flag = 1;

	for (int j = 0; j < son[i]; j++) {

	    if (s[i][j].wei >= Min) {

		flag = 0;

		tmp += s[i][j].money;

		break;

	    }

	}

	if (flag || tmp > sum)	return false;

    }

    return true;

}

int main() {

    State now;

    int cas, n, cur, L, R;

    scanf("%d", &cas);

    while (cas--) {

	memset(s, 0, sizeof(s));

	memset(son, 0, sizeof(son));

	memset(str, 0, sizeof(str));

	cnt = L = R = 0;

	scanf("%d%d", &n, &sum);

	for (int i = 0; i < n; i++) {

	    scanf("%s%s%d%d", sex, now.name, &now.money, &now.wei);

	    if (now.wei > R)	R = now.wei;

	    cur = find(sex);

	    s[cur][son[cur]++] = now;

	    if (cur == cnt) cnt++;

	}

	for (int i = 0; i < cnt; i++)

	    sort(s[i], s[i] + son[i], cmp);

	int mid;

	while (L < R) {

	    mid = (L + R) / 2;

	    if (L == mid)   break;

	    if (judge(mid))

		L = mid;

	    else

		R = mid;

	}

	if (judge(mid + 1)) mid++;

	printf("%d\n", mid);

    }

    return 0;

}

巴特西

uvalive 3971 - Assemble(二分搜索 + 贪心）

最新文章

热门文章