C. Sonya and Robots

题目链接

Codeforces Round #495 (Div. 2)--C. Sonya and Robots

题解

中档题。题意大概是给定一串序列,两个机器人分别从左往右与从右往左移动,遇到和自己相同的数字时停下,求出使两个机器人不相遇的序列数目。
首先统计出每个数字的数目及数字的总数量,从左往右扫描。如果当前数字没有当做过左边机器人的值,则把答案加上右侧剩余数字的数目,最终得出结果。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, rnum;
int a[100005], l[100005], r[100005];
long long ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (!r[a[i]])rnum++;
        r[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        r[a[i]]--;
        if (!r[a[i]])rnum--;
        if (l[a[i]])continue;
        l[a[i]]++;
        ans += rnum;
    }
    cout << ans;
}

标签: implementation

添加新评论