題意:
給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; }
矩陣的乘法算法,矩陣乘法算法本文地址:http://www.
每次可以翻動一個、二個或三個硬幣。(Mock Turt
Boost::bind使用詳解,boostbind使用詳解1
大話設計模式C++實現 -組合模式 一、UML圖 &n
HDU3234&&UVA12232&
C++Builder編寫計算器,builder編寫計算器用C