hdu 5720(贪心)

题目链接：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(贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。