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