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

Re:觉得这道题的贪心算法也不是很好想啊,想了很久才有一点搞懂为什么这个贪心算法对

Posted by houzhe at 2022-01-17 08:22:51 on Problem 3614
In Reply To:觉得这道题的贪心算法也不是很好想啊,想了很久才有一点搞懂为什么这个贪心算法对 Posted by:houzhe at 2022-01-17 08:11:17
贴个代码留个纪念吧:
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <sstream>
#include <math.h> 
#include <string.h>
#include <algorithm>
#include <numeric>
#include <deque>
#include <climits>

using namespace std;

typedef long long ll;

// const double M_PI = acos(-1.0);
// const double E = 2.71828182845904523536029;

const int MAX_SPF = 1010;

int bottleSpfs[MAX_SPF];

struct Cow {
	int minSpf, maxSpf;
	Cow(int i, int a) : minSpf(i), maxSpf(a) {}
};
bool operator<(const Cow& c1, const Cow& c2) {
	if (c1.maxSpf == c2.maxSpf)
		return c1.minSpf > c2.minSpf;
	return c1.maxSpf < c2.maxSpf;
}

int main() {
	vector<Cow> cows;
	int c, l;
	cin >> c >> l;

	for (int i = 0; i < c; i++) {
		int minSpf, maxSpf; cin >> minSpf >> maxSpf;
		cows.push_back(Cow(minSpf, maxSpf));
	}

	sort(cows.begin(), cows.end());

	for (int i = 0; i < l; i++) {
		int spf, cover;
		cin >> spf >> cover;
		bottleSpfs[spf] += cover;
	}

	int ans = 0;

	for (int i = 0; i < cows.size(); i++) {
		for (int j = cows[i].minSpf; j <= cows[i].maxSpf; j++) {
			if (bottleSpfs[j] > 0) {
				ans++;
				bottleSpfs[j]--;
				break;
			}
		}
	}

	cout << ans << endl;

	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