这次的题好奇怪哦。。。
思路：先把跟停车位相邻的车停进去，然后开始转圈。。。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int> using namespace std; const int N = ;
const int M = 1e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +; int a[][N], n, k;
vector<int> ans[]; pii getPos(int id) {
if (id < n) return mk(, id);
else return mk(, * n - - id);
} void add(int x, int y, int z) {
ans[].push_back(x);
ans[].push_back(y);
ans[].push_back(z);
} int main() {
scanf("%d%d", &n, &k); for(int i = ; i < ; i++) {
for(int j = ; j < n; j++) {
scanf("%d", &a[i][j]);
}
} for(int j = ; j < n; j++) {
if(a[][j] == ) continue;
if(a[][j] == a[][j]) {
add(a[][j], , j);
k--;
a[][j] = ;
}
} for(int j = ; j < n; j++) {
if(a[][j] == ) continue;
if(a[][j] == a[][j]) {
add(a[][j], , j);
k--;
a[][j] = ;
}
} if(k == * n) {
puts("-1");
return ;
} while(k > ) {
for(int i = ; i < * n; i++) {
pii u = getPos(i);
if(a[u.first][u.second] == ) continue;
if(a[u.first ^ ][u.second] == a[u.first][u.second]) {
add(a[u.first][u.second], u.first ^ , u.second);
k--;
a[u.first][u.second] = ;
continue;
} pii v = getPos((i + * n - ) % ( * n));
if(a[v.first][v.second] != ) continue;
add(a[u.first][u.second], v.first, v.second);
swap(a[u.first][u.second], a[v.first][v.second]);
}
} printf("%d\n", ans[].size());
for(int i = ; i < ans[].size(); i++) {
printf("%d %d %d\n", ans[][i], ans[][i] + , ans[][i] + );
} return ;
}
E：
题目大意：给你n个长度小于1e6的向量，让你把每个向量变成正向或者负向，使得所有向量加起来的长度不超过1.5 * 1e6
思路：正解是每三个向量中都能找到两个向量合起来 <= 1e6，然后不断合并，最后只会剩下一个或者两个向量，
如果一个向量肯定 <= 1e6， 如果是两个向量一定 <= 1.5 * 1e6。。。
但是可以用随机洗牌的方法去贪心，因为能卡掉的数据特别不好造。。。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int> using namespace std; const int N = 1e5 + ;
const int M = 1e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +; int n, ans[N], id[N];
LL base = 1500000ll * ;
struct Vector {
Vector(LL x = , LL y = ) {
this->x = x;
this->y = y;
} Vector operator + (const Vector &rhs) const {
return Vector(x + rhs.x, y + rhs.y);
} Vector operator - (const Vector &rhs) const {
return Vector(x - rhs.x, y - rhs.y);
} LL len() {
return x * x + y * y;
} LL x, y, id;
}a[N]; int main(){
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lld%lld", &a[i].x, &a[i].y);
id[i] = i;
} while() {
random_shuffle(id + , id + n);
Vector now;
for(int i = n; i >= ; i--) {
int pos = id[i];
Vector nx1 = now + a[pos];
Vector nx2 = now - a[pos];
if(nx1.len() <= nx2.len()) {
now = nx1;
ans[pos] = ;
} else {
now = nx2;
ans[pos] = -;
}
} if(now.len() <= base) {
for(int i = ; i <= n; i++) {
printf("%d ", ans[i]);
}
puts("");
return ;
}
}
return ;
} /*
*/