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

【题意】

在这里输入题意

【题解】

处理出所有的线
其实就是区间。
总共有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;
}
05-15 14:11