# Codeforces 1791 G2. Teleporters (Hard Version)
###### tags: `codeforces` `binary search`

[題目連結](https://codeforces.com/contest/1791/my)

# Method Sort + Binary search
:::info
:bulb: **Concept**:
1. 將從兩邊出發的coin 由小至大排序, 只要coin總和 小於等於 初始 coin即可.
case 1: 前面所選的位置包含從左邊出發的位置
直接計算數量回傳即可

case 2: 前面所選的位置**不包含**從左邊出發的位置
表示全部都是從右邊出發.
採用binary search的作法

2. binary search 作法
從case 2可以得知付出最少coin都是從右邊出發的,
但是題目要求第一次必須從左邊出發,
因此我們透過對右邊出發所需要的coin做排序,
然後每次假設從 左邊 index 0 ~ n-1 出發,
透過binary search 搜尋 從右邊出發還可以獲得多少個位置.

:::

TC: O(NlogN) SC: O(N)
完整程式碼

#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <chrono>
#include <iostream>
#include <string>
using namespace std;


typedef long long int ll;
const int mod = 998244353;
#define INF 1e9
#define CLR(a) memset(a, 0, sizeof(a))
#define SET(a, val) memset(a, val, sizeof(a))

#define N 200005
ll nums[N];
pair<ll, int> left_nums[N];
pair<ll, int> right_nums[N];
ll sum_nums[N];

bool visited[N];


int binary_search(int i, ll n, ll c)
{
    int idx = right_nums[i].second;
    int l = 0;
    int r = n - 1;

    if (c < (nums[idx] + idx + 1)) {
        return 0;
    }

    c -= (nums[idx] + idx + 1);

    while (l < r) {
        int m = r - (r - l) / 2;
        ll dup = (m > i) ? right_nums[i].first : 0;
        if (c >= (sum_nums[m] - dup)) {
            l = m;
        }
        else {
            r = m - 1;
        }

    }

    return l + (i >= l);
}

int do1(ll n, ll c)
{
    int lidx = 0;
    int ridx = 0;
    bool used_left = false;
    int output = 0;

    for (int i = 1; (i <= n); i++) {
        while (visited[left_nums[lidx].second]) {
            lidx++;
        }
        while (visited[right_nums[ridx].second]) {
            ridx++;
        }

        if (c < min(left_nums[lidx].first, right_nums[ridx].first)) {
            break;
        }

        if (left_nums[lidx] <= right_nums[ridx]) {
            c -= left_nums[lidx].first;
            visited[left_nums[lidx].second] = true;
            lidx++;
            used_left = true;
        }
        else {
            c -= right_nums[ridx].first;
            visited[right_nums[ridx].second] = true;
            ridx++;
        }

        output++;
    }

    return used_left ? output : 0;
}

void solve(int round)
{
    ll n, c, cur_c;
    
    
    int output = 0;
    
    CLR(nums);
    CLR(visited);
    CLR(left_nums);
    CLR(right_nums);
    CLR(sum_nums);

    cin >> n >> c;
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        left_nums[i] = { nums[i] + i + 1, i };
        right_nums[i] = { nums[i] + n - i, i };
    }

    sort(left_nums, left_nums + n);
    sort(right_nums, right_nums + n);
 
    output = do1(n, c);
    if (output > 0) {
        printf("%d\n", output);
        return;
    }
    
    for (int i = 0; i < n; i++) {
        sum_nums[i + 1] = sum_nums[i] + right_nums[i].first;
    }
    for (int i = 0; i < n; i++) {
        output = max(output, binary_search(i, n, c));
    }

    printf("%d\n", output);
}