运维开发网

cf 1004 C Sonya and Robots

运维开发网 https://www.qedev.com 2020-05-13 10:36 出处:网络 作者:运维开发网整理
cf 1004 C Sonya and Robots 题意 给你n个数字\(a_i\) ,在数字的左边和右边各有一个机器人,分别给左边和右边的机器人一个数字\(a_i\), \(a_j\),左边的机器人往右走,右边的机器人往左走,左边的机器人遇到\(a_i\)就停,右边的机器人遇到\(a_j\)就停,问使得两个机器人不相遇的对数有多少对? 题解 就是求一个数(第一次出现的)后面有多少个不同的数,如

cf 1004 C Sonya and Robots

题意

给你n个数字\(a_i\) ,在数字的左边和右边各有一个机器人,分别给左边和右边的机器人一个数字\(a_i\), \(a_j\),左边的机器人往右走,右边的机器人往左走,左边的机器人遇到\(a_i\)就停,右边的机器人遇到\(a_j\)就停,问使得两个机器人不相遇的对数有多少对?

题解

就是求一个数(第一次出现的)后面有多少个不同的数,如果不是第一次出现的数,就是0,因为在该数前面已经有一个和他一样的数了,机器人肯定在前面就停了,不可能走到这里,所以就是预处理一下,就可以了。

#include <cstdio>
#include <cstring>
int cnt[100010], b[100010];
int main() {
    int n, a[100010], c = 0;
    long long ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = n - 1; i >= 0; i--) {
        b[i] = c;
        cnt[a[i]]++;
        if(cnt[a[i]] == 1) c++;

    }
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) {
        if(cnt[a[i]] == 0) ans += b[i];
        cnt[a[i]]++;
    }
    printf("%I64d\n", ans);
    return 0;
}
0

精彩评论

暂无评论...
验证码 换一张
取 消