Codeforces Round #274 (Div. 2) - c++编程基础

只会由三种0,1,2,

题目大意：

给出一把尺子，总长度为l，其中有n个标记，其中第一个标记为0, 第n个标记为l。要求量出x和y，如若不能量出，可以在上面增加标记。要求增加的标记最少。

由题意可知，标记增加量为：0, 1, 2;

0个为x和y都可以在尺子上找到，即a[i]+x和a[i]+y均可在尺子上找到，我们可以采用二分搜索。复杂度为O(nlogn)(可以用STL自带的)

1个为可以在上面标记一个点，使得x和y都可以在尺子上找到，即a[i]+x+y , a[i]+x-y, a[i]-x+y, a[i]+x, a[i]+y，其中一个可以在尺子上找到就可以了。

2个直接标记x,y就够了。

a[i] - a[j] = y-x;

a[i] - a[j = x-y;(存在这种差的话也可以加一个)

#include 
                              
                               
#include 
                               
                                 #include 
                                
                                  #include 
                                 
                                   using namespace std; const int maxn = 1e5+10; int a[maxn]; int n,l,x,y; bool check_0() { int fx,fy; fx = fy = 0 ; for(int i = 0; i < n; i++) { if(binary_search(a,a+n,a[i]+x) && a[i]+x >=0 && a[i]+x <= l) { fx = 1; } if(binary_search(a,a+n,a[i]+y) && a[i]+y >= 0 && a[i] + y <= l) { fy = 1; } } if(fx && fy) return true; else return false; } bool check_1() { for(int i = 0; i < n; i++) { if(binary_search(a,a+n,a[i]+x) && y >=0 && y <= l) { cout<<1<
                                  
                                   = 0 && x <= l) { cout<<1<
                                   
                                    = 0 && a[i] -x <= l) { cout<<1<
                                    
                                     = 0 && a[i] + x <= l) { cout<<1<
                                     
                                      = 0 && a[i] + y+x <= l) { cout<<1<
                                      
                                       >n>>l>>x>>y) { for(int i = 0; i < n; i++) { cin>>a[i]; } if(check_0()) { cout<<0<

Codeforces Round #274 (Div. 2)(四)

题目大意：