【链接】h在这里写链接

【题意】

你有n个位置,然后其中有k个地方是已经被人占据了的.

一个“好的位置”的定义是指,这个位置相邻的地方其中至少有一个被人占据了。

k个被人占据的位置是不确定的,由你决定。

问你最少的和最多的“好的位置”的个数。

【题解】

肯定是010 010 010...这样的安排最优。

也就是3个3个地安排,然后中间放一个被占据的位置。

如果k<=n/3,那么答案就是2*k,因为每个被占据的位置都能产生两个好的位置。

如果k>n/3

如果n%3==0,那么答案就是2*(n/3)-(k-n/3),因为多出来的被占据的位置,只能去填0了,答案就会减少(k-n/3);

如果n%3==1,也即010 010 _,这个_填0也没用,干脆用来填这个1(多余的,k--),这样就能尽量少的减少“好的位置了”

如果n%3==2,也即010 010 _ _,这里_ _中填01是最优的,则会发现和n%3==0的情况是一样的,多出来的k,每填一个

0就会减少一个"好的位置",没办法减.

至于最小的答案,除非n==k,或k==0,其他都是1,否则为0

【错的次数】

【反思】

写的时候太冲动了,没有认真思考。

【代码】

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <queue>

#include <iomanip>

#include <set>

#include <cstdlib>

#include <cmath>

#include <bitset>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb emplace_back

#define fi first

#define se second

#define ld long double

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x)

#define rf(x) scnaf("%lf",&x)

#define oi(x) printf("%d",x)

#define ol(x) printf("%lld",x)

#define oc putchar(' ')

#define os(x) printf(x)

#define all(x) x.begin(),x.end()

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

#define sz(x) ((int) x.size())

#define ld long double

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

//mt19937 myrand(time(0));

//int get_rand(int n){return myrand()%n + 1;}

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

int n,k;

int main(){

    //Open();

    //Close();

    ri(n),ri(k);

    int mi;

    if (n > k && k >0)

        mi = 1;

    else

        mi = 0;

    if (n==1){

        puts("0 0");

        return 0;

    }

    int temp = n/3;

    int ju = n%3;

    int ma = temp*2;

    if (k <= temp){

        ma-= (temp-k)*2;

    }else{

        // k > temp

        if (ju==1){

            k--;

        }

        if (ju==2){

            k--;

            ma++;

        }

        ma -= (k-temp);

    }

    oi(mi),oc,oi(ma),puts("");

    return 0;

}

巴特西

【Codeforces Round #433 (Div. 2) B】Maxim Buys an Apartment