題意:
給n個區間 選擇盡量少的區間 覆蓋1~T這個區間
如果不能覆蓋 輸出-1
思路:
經典貪心 區間覆蓋
將所有區間按照起點從小到大排序 取終點在最右邊的那個區間
code:
#include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 0x3f3f3f3f #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) typedef pair pii; typedef long long LL; //------------------------------ const int maxn = 25005; int n, T; struct node{ int s,e; bool operator < (const node nt) const{ return s < nt.s; } }cow[maxn]; void init(){ for(int i = 0; i < n; i++){ scanf("%d%d",&cow[i].s,&cow[i].e); } sort(cow, cow + n); } void solve(){ if(cow[0].s > 1){ printf("-1\n"); return; } int start_ = 1, end_ = 1, cnt = 1; for(int i = 0; i < n; i++){ if(cow[i].s <= start_) end_ = max(end_, cow[i].e); else{ cnt++; start_ = end_ + 1; if(cow[i].s <= start_) end_ = max(end_, cow[i].e); else{printf("-1\n"); return; } } if(end_ >= T) break; } if(end_ >= T) printf("%d\n",cnt); else printf("-1\n"); } int main(){ scanf("%d%d",&n,&T); init(); solve(); return 0; }
作用:用原型實例指定創建對象的種類,並且通過拷
在項目中需要用到程序更新的功能,同事介紹說是c
說明:一、本程序是一個斜視角地圖的滾屏演示。本
一、簡單介紹ostringstream是C++
多年以來,只要提到編寫Windows服務,就會
題目 Given a string s consists