【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
处理出所有的线
其实就是区间。
总共有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;
}