首页 > 代码库 > hdu 5037
hdu 5037
http://acm.hdu.edu.cn/showproblem.php?pid=5037
贪心 最初WA了一次,做法就是看石头间距pos[i+1]-pos[i] <=L直接跳,否则ans++;非常愚蠢
1,2,3 这个例子就能破掉这种策略
所以其实一个比较重要的问题在于处理上一步到下一步的剩余问题
参考了http://blog.csdn.net/u014569598/article/details/39471913
正确的策略是,记录上一次跳的长度,如果这次遇到的石子的间距x x+last_len <=L 那么上次就能把这个x也跳掉,
要说从这道题里收获了什么,应该就是 找出两次决策之间的关系,想想怎么处理上次决策剩余。尤其别忽略相邻两次决策的关系
所以就是下面的代码,注意注释
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <set> #include <queue> #include <cmath> using namespace std; const int MAXN = 2*1e5+50; int pos[MAXN]; int main() { int ncase,ic=0; int n,m,L; scanf("%d",&ncase); while(ncase--) { scanf("%d%d%d",&n,&m,&L); for(int i=1;i<=n;i++) scanf("%d",&pos[i]); int ans=0,dis=L; pos[0]=0; pos[++n]=m; sort(pos,pos+n); for(int i=0;i<n;i++) { //dis+=pos[i+1]-pos[i]; int x=(pos[i+1]-pos[i])%(L+1); int y=(pos[i+1]-pos[i])/(L+1); if(dis+x>=L+1) { dis=x;//虽然dis<=L 但是需要跳一步,因为下一块石子的距离加上的话,会超过L ans+=1+2*y; //L+1需要跳两步 } else { dis+=x; // dis+x<=L 所以一步就跳过好几个石子 ans+=2*y; } //if(pos[i+1]-pos[i] <=L)continue; //ans+=(pos[i+1]-L-pos[i]); } printf("Case #%d: %d\n",++ic,ans); } return 0; }
hdu 5037
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。