| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:觉得这道题的贪心算法也不是很好想啊,想了很久才有一点搞懂为什么这个贪心算法对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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator