Codeforces Round #673 (Div. 2) A

题目链接

A. Copy-paste

代码：

const int N = 1e3 + 10;

int a[N];

int main() {

    int t; cin >> t;
    while(t --) {
        int n, k; cin >> n >> k;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        int ans = 0;
        sort(a + 1, a + n + 1);
        int mn = a[1];
        for(int i = 2; i <= n; i ++) {
            int d = k - a[i];
            ans += d / mn;
        }
        cout << ans << endl;
    }
    return 0;
}

B. Two Arrays

思路：

如果 (2 imes a[i] = T)，那么就把 (a[i]) 平均放在两边，多出一个就任意。

否则：就把 (a[i]) 放在一边， (T - a[i]) 放在另一边。

代码：

const int N = 1e5 + 10;

int a[N], ans[N];

map<int, int> mp1, mp2, mp3;

int main() {

    int t; cin >> t;
    while(t --) {
        mp1.clear();
        mp2.clear();
        mp3.clear();
        int n, T; cin >> n >> T;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        for(int i = 1; i <= n; i ++) { mp1[a[i]] ++; mp2[a[i]] ++; }
        for(int i = 1; i <= n; i ++) {
            if(T - a[i] == a[i]) {
                if(mp1[a[i]] > mp2[a[i]] / 2) ans[i] = 0;
                else ans[i] = 1;
                mp1[a[i]] --;
            } else {
                if(a[i] > T - a[i]) ans[i] = 0;
                else ans[i] = 1;
            }
        }
        for(int i = 1; i <= n; i ++) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

C. k-Amazing Numbers

思路：

找出相同两个数之间距离的最大值，对于每个数而言，默认第 (0) 个数和第 (n + 1) 个数与自己相同。

那么对于每个距离，我们可以找出其中对应的最小值。需要注意的是：短距离合法的，长距离一定合法。

这代码真的丑。

代码：

const int N = 3e5 + 10;

int a[N];
int ans[N];

map<int, int> mp1, mp2;

int main() {

    int t; cin >> t;
    while(t --) {
        mp1.clear();
        mp2.clear();
        int n; cin >> n;
        for(int i = 1; i <= n; i ++)  cin >> a[i]; 
        for(int i = 1; i <= n; i ++) {
            if(mp1[a[i]]) mp2[a[i]] = max(mp2[a[i]], i - mp1[a[i]]);
            else mp2[a[i]] = i;
            mp1[a[i]] = i;
        }
        for(int i = 1; i <= n; i ++) {
            mp2[a[i]] = max(mp2[a[i]], n - mp1[a[i]] + 1);
        }
        mp1.clear();
        for(auto it : mp2) {
            if(mp1[it.y] == 0) mp1[it.y] = it.x;
            else mp1[it.y] = min(mp1[it.y], it.x);
        }
        int tmp = INF;
        for(int i = 1; i < n; i ++) {
            if(mp1[i]) {
                ans[i] = min(tmp, mp1[i]);
                tmp = min(tmp, mp1[i]);
            } 
            else if(tmp != INF) ans[i] = tmp;
            else ans[i] = -1;
        }
        ans[n] = *min_element(a + 1, a + n + 1);
        for(int i = 1; i <= n; i ++) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}