怎么进入凡科建设的网站,网页版微信登录显示二维码已失效,wordpress 判断版本号,大型网页游戏有哪些CSES - 1632 Movie Festival II 原题链接分析程序代码 原题链接
CSES - 1632 Movie Festival II
分析
这题需要用到贪心的策略#xff0c;即先结束的电影先安排#xff0c;这样才能看尽可能多的电影。这题可以归类为区间问题#xff0c;先按照结束时间对区间进行升序排序… CSES - 1632 Movie Festival II 原题链接分析程序代码 原题链接
CSES - 1632 Movie Festival II
分析
这题需要用到贪心的策略即先结束的电影先安排这样才能看尽可能多的电影。这题可以归类为区间问题先按照结束时间对区间进行升序排序。用大小为k的multiset维护电影的结束时间。区间遍历的过程中找multiset中最大小于当前结束时间的元素若找到则可观看的电影数加一同时更新multiset。
程序代码
#include iostream
#include vector
#include algorithm
#include queue
#include set
using namespace std;typedef pairint, int PII;bool cmp(PII a, PII b)
{if(a.second b.second) return true;else if(a.second b.second) return false;else {return a.first b.first;}
}int main()
{int n, k;cin n k;vectorPII v(n);int a, b;for(int i 0; i n; i) {cin a b;v[i] {a, b};}sort(v.begin(), v.end(), cmp);multisetint ms;for(int i 0; i k; i) {ms.insert(0);}int res 0;for(auto t : v) {// 返回一个迭代器该迭代器指向刚好大于key的下一个元素// 若所有元素均大于key返回begin()// 若所有元素均小于key返回ms.end()auto it ms.upper_bound(t.first);if( it begin(ms) ) continue;ms.erase(--it);res;ms.insert(t.second);}cout res endl;return 0;
}
