锐客网

  1. 首页 > it技术 > >

Codeforces22|Codeforces22 D. Segments（贪心）

题意： 在坐标轴上给定 n 条线段，有 k 个点，使这 n 条线段都至少有一个点在其上面（恰在端点也行）。
求 k 的最小值，并给出一个k最小时的方案。
数据范围：n<=1e3
解法： 将线段按右端点从小到大排序，
遍历，遇到未被标记的线段，贪心地在右端点插一个点，然后把这个点插到的线段标记。
【Codeforces22|Codeforces22 D. Segments（贪心）】复杂度O(n2)
code：

#include using namespace std; const int maxm=1e3+5; struct Node{ int l,r; }a[maxm]; int mark[maxm]; int n; bool cmp(Node a,Node b){ if(a.r!=b.r)return a.r>n; for(int i=1; i<=n; i++){ cin>>a[i].l>>a[i].r; if(a[i].l>a[i].r)swap(a[i].l,a[i].r); //数据可能l>r } sort(a+1,a+1+n,cmp); vectorans; for(int i=1; i<=n; i++){ if(mark[i])continue; int p=a[i].r; ans.push_back(p); for(int j=i+1; j<=n; j++){ if(a[j].l<=p&&a[j].r>=p){ mark[j]=1; } } } cout<

    推荐阅读


    上一篇：新年记事（二）

    下一篇：Codeforces580|Codeforces580 D. Kefa and Dishes（状压dp）