題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5720

題意：地上有n根樹枝， 長度都給出來了，你手上有長度范圍為[L, R]的樹枝，問有多少樹枝不能和地上任意兩根樹枝組成三角形

思路：先sort一遍地上的樹枝a[]，發現相鄰兩根樹枝包含了兩根中任意一根和剩下的樹枝中任意一根的所有情況；

1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <cstdio> 7 #include <vector> 8 #include <ctime> 9 #include <cmath> 10 #include <queue> 11 #include <set> 12 #include <map> 13 using namespace std; 14 #define Fill(x, y) memset((x), (y), sizeof(x)) 15 #define Rep(i, x, y) for(int i = x; i <= y; ++i) 16 #define Dow(i, x, y) for(int i = x; i >= y; --i) 17 typedef long long LL; 18 typedef pair <int, int> P; 19 const int N = 1e5 + 10; 20 int GCD(int a, int b) { 21 return b ? GCD(b, a % b) : a; 22 } 23 int LCM(int a, int b) { 24 return a * b / GCD(a, b); 25 } 26 27 LL a[N]; 28 struct data { 29 LL l , r; 30 }x[N]; 31 LL cmp(data x , data y) { 32 if(x.l == y.l) 33 return x.r > y.r; 34 return x.l < y.l; 35 } 36 37 int main() 38 { 39 int t , n; 40 LL L , R; 41 scanf("%d" , &t); 42 while(t--) { 43 scanf("%d %lld %lld" , &n , &L , &R); 44 Rep(i , 1 , n) { 45 scanf("%lld" , a + i); 46 } 47 sort(a + 1 , a + n + 1); 48 x[1].l = 1, x[1].r = 0; 49 int k = 1; 50 Rep(i , 2 , n) { 51 LL x1 = a[i] - a[i - 1] + 1; 52 LL y1 = a[i] + a[i - 1] - 1; 53 if(x1 > R || y1 < L) 54 continue; 55 if(x1 < L) 56 x1 = L; 57 if(y1 > R) 58 y1 = R; 59 x[k].l = x1, x[k].r = y1; 60 k++; 61 } 62 sort(x + 1 , x + k , cmp); 63 LL res = x[1].r - x[1].l + 1; 64 // cout << res << endl; 65 LL ll = x[1].l, rr = x[1].r; 66 for(int i = 2 ; i < k ; ++i) { 67 if(x[i].l <= rr) 68 { 69 if(x[i].r > rr) 70 { 71 res += x[i].r - rr; 72 ll = x[i].l, rr = x[i].r; 73 } 74 } 75 else if(x[i].l > rr) 76 { 77 res += x[i].r - x[i].l + 1; 78 ll = x[i].l, rr = x[i].r; 79 } 80 //cout << res << endl; 81 } 82 LL res1 = R - L + 1 - res; 83 printf("%lld\n" , res1); 84 } 85 return 0; 86 }

?

轉載于:https://www.cnblogs.com/luomi/p/5679817.html

總結

以上是生活随笔為你收集整理的hdu5720_贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。