Codeforces 480B Long Jumps 规律题 - c++编程基础

TOP

Codeforces 480B Long Jumps 规律题

2015-07-20 17:25:40 来源: 作者: 【大中小】浏览:3次

Tags：Codeforces 480B Long Jumps 规律

题目链接：点击打开链接

题意：

输出n l x y

有一根直尺长度为l

上面有n个刻度。

下面n个数字是距离开头的长度（保证第一个数字是0，最后一个数字是l）

要使得直尺中存在某2个刻度的距离为x ，某2个刻度的距离为y

要添加最少几个刻度。

问：

最少的刻度个数

输出标记的位置。

思路：

分类讨论一下。。

若本身尺子里就有x、y就输出0

若只有x 或只有y就输出一个刻度。

若2个都没有就：

1、加1个刻度ans，这个ans是距离某个刻度距离为x的，然后看一下是否有距离ans为y的刻度，若有则添加一个ans即可。

2、第1个都非法时就直接加2个刻度。

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           template 
          
            inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template 
           
             inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; const int N = 200050; vector
            
             G; bool Find(ll x){ for(int i = G.size()-2; i > 0; i--) { if(G[i] - x < 0)return false; if( G[lower_bound(G.begin(), G.end(), G[i] - x) - G.begin()] == G[i] - x) return true; } return false; } ll n, l, x, y; ll go(){ ll ans; for(int i = G.size()-2; i > 0; i--){ ans = G[i]-x; if(ans >= 0 && ((ans+y<=l&&G[lower_bound(G.begin(), G.end(), ans+y) - G.begin()] == ans+y) || (ans-y>=0&&G[lower_bound(G.begin(), G.end(), ans-y) - G.begin()] == ans-y))) return ans; ans = G[i]+x; if(ans <= l && ((ans + y <= l && G[lower_bound(G.begin(), G.end(), ans+y) - G.begin()] == ans+y) || (ans-y>=0&&G[lower_bound(G.begin(), G.end(), ans-y) - G.begin()] == ans-y))) return ans; } return -1; } void input(){ G.clear(); G.push_back(-5000000001LL); ll tmp; while(n--){ rd(tmp); G.push_back(tmp); } G.push_back(1e10); } int main() { while(cin>>n>>l>>x>>y){ input(); int havx = Find(x), havy = Find(y); if(havx + havy == 2) puts("0"); else if(havx + havy == 1) { if(havx) printf("1\n%I64d\n", y); else printf("1\n%I64d\n", x); } else { ll ans = go(); if(ans == -1) { printf("2\n%I64d %I64d\n", x, y); } else printf("1\n%I64d\n", ans); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 1827 Summer Holiday（强连通..	下一篇：HDoj -3351- Seinfeld -栈的简单..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: