The Weakest Sith

http://codeforces.com/gym/101149/problem/F

题目要输出最丑陋的衣服。所以每件衣服都要和其他衣服比一次。

但是注意到，能赢一件衣服的衣服，就算是好衣服了。

那么，可以选1做起始点，然后向后比较，如果后面的能赢比较点，那么这件就是好衣服了。

如果不能，那么证明起始点那件衣服是好衣服。当前这件衣服不确定，所以就重新选这件衣服做起吃点，去比较。

有可能会1赢7,7赢8但是8赢2这样，就是说可能要往前比较一次。

所以把数组写两次就可以了。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn = 2e5 + ;

struct node {

    int a, b, c;

    bool operator == (const struct node & rhs) const {

        return a == rhs.a && b == rhs.b && c == rhs.c;

    }

}arr[maxn * ];

bool iswin[maxn * ];

bool check(struct node a, struct node b) { //b打赢a

    if (b.a > a.a && b.b > a.b) return true;

    if (b.a > a.a && b.c > a.c) return true;

    if (b.b > a.b && b.c > a.c) return true;

    return false;

}

void work() {

    int n;

    cin >> n;

    for (int i = ; i <= n; ++i) {

        cin >> arr[i].a >> arr[i].b >> arr[i].c;

        arr[i + n] = arr[i];

    }

    int ans = ;

    struct node now = arr[];

    int id = ;

    for (int i = ; i <=  * n; ++i) {

        if (now == arr[i]) continue;

        if (check(now, arr[i])) {

            iswin[i] = true;

        } else {

            iswin[id] = true;

            now = arr[i];

            id = i;

        }

    }

    for (int i = ; i <= n; ++i) {

        ans += iswin[i] == false;

    }

    cout << ans << endl;

    for (int i = ; i <= n; ++i) {

        if (iswin[i] == false) {

            cout << i << endl;

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    IOS;

    work();

    return ;

}

巴特西

The Weakest Sith

最新文章

热门文章