首页 > 代码库 > hdu 5037 Frog(贪心)
hdu 5037 Frog(贪心)
分析:贪心吧,让三个石头第一个和第三个距离为L+1,并让每次跳的点尽量小。
石头是可能无序的,比赛是实在没发现,就加了个排序过了,哎。。。
和代码一起讲做法吧,假设情况1 :上一步k加这一步余数x大于L,则最后剩余部分需要单独跳;情况2:上一步k加这一步余数x小于等于L,最后剩余部分可以并进上一步,即k+x。
画了一张图;
代码:
#include<iostream> #include<queue> #include<map> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<algorithm> #define MOD 1000000007 typedef long long ll; using namespace std; const int maxn=200005; int da[maxn]; int main() { int T,n,m,l,cas=0; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&l); for(int i=1;i<=n;i++) scanf("%d",&da[i]); da[++n]=m;da[0]=0; int ans=0; int k=l;//k表示上次跳的距离,用此限制下次的跳越 sort(da,da+n); for(int i=1;i<=n;i++) { int x=(da[i]-da[i-1])%(l+1); int y=(da[i]-da[i-1])/(l+1); if(k+x>=l+1) { k=x; ans+=y*2+1; } else if(k+x<l+1) { k=x+k; ans+=y*2; } } printf("Case #%d: %d\n",++cas,ans); } return 0; }
hdu 5037 Frog(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。