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

官方題解：

考慮三角形三條邊a,b,c? (a≥b)?的關系a?b<c,a+b>c?，即c∈(a?b,a+b)?。令加入的邊為c?，枚舉所有邊作為a?的情況。對于所有可行的b?，顯然與a?相差最小的可以讓(a?b,a+b)?覆蓋范圍最大，所以可以貪心地選擇不大于a?的最大的b?。于是我們可以先將邊按長度排序，然后a?i??和a?i+1??建一條線段。線段并是不合法的部分。將所有線段按左端點排序，按序掃描一遍，過程中統計答案即可。時間復雜度O(Tn?logn)?。 ?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;typedef long long LL; typedef pair<LL,LL> Pi; LL x[100005]; Pi pr[100005];int main() {int t;scanf("%d",&t);while(t--){int n;LL L,R;scanf("%d%lld%lld",&n,&L,&R);for(int i = 0; i < n; ++i) scanf("%lld",&x[i]);sort(x,x+n);for(int i = 0; i < n-1; ++i){pr[i].first = x[i+1]-x[i];pr[i].second = x[i+1]+x[i];}sort(pr,pr+n-1);LL ans = 0;LL mx = L;for(int i = 0; i < n-1 && pr[i].first <= R; ++i){if(pr[i].first >= mx) ans += (pr[i].first-mx+1);mx = max(mx,pr[i].second);}ans += max(0LL,R+1-mx);printf("%lld\n",ans);}return 0; }

總結

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

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