【Codeforces Round #455 (Div. 2) B】Segments

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

处理出所有的线
其实就是区间。
总共有n*(n+1)/2个
然后按照左端点、右端点排序

每次取最左边的线。

多种可能就取右端点尽量小的线。

v[i]i是左端点,里面的东西是右端点。

每个v[i]都从大到小排。

则每次取v[i]的最末端就可以了。

->然后作为新的x

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 100;

int n;

vector <int> v[N+10];

int GetFirst(int temp){

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

        if (v[i].size()>0){

            return i;

        }

    return -1;

}

int main(){

	#ifdef LOCAL_DEFINE

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

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

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

        for (int j = 1;j <= n;j++){

            int y = i+j;

            if (y>n) break;

            v[i].push_back(y);

        }

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

        sort(v[i].begin(),v[i].end());

        reverse(v[i].begin(),v[i].end());

    }

    int cnt = 0;

    int x = GetFirst(0);

    while (x!=-1){

        cnt++;

        int y = v[x].back();

        v[x].pop_back();

        x = GetFirst(y);

        while (x!=-1){

            y = v[x].back();

            v[x].pop_back();

            x = GetFirst(y);

        }

        x = GetFirst(0);

    }

    cout << cnt << endl;

	return 0;

}