牛客周赛136F题
原文链接：https://www.cnblogs.com/Time25/p/19766257.html
原题大意
（https://ac.nowcoder.com/acm/contest/130107/F）
给你n个点，让你构造一个图像，这个图像只能由k对相邻的
分析
要在最多用n个点把这恰好k对给配出来，可以想到的就是贪心一下，尽量用最少的n构造出这恰好k个，剩下的呢？因为已经有了k条边是相邻的，所以剩下的n个点之间不可以有曼哈顿距离为1的组合
就是之间隔一个，并且距离在正无穷，也就是题目说的1e9，就是1000000000LL1
2
3
4
5
6
7
8for(int i=0;n>0;n--,i+=2){
cout<<1000000000LL<<" "<<i<<endl;
}
for(int i=0;i<=l+1;i++){
for(int j=0;j<=l+1;j++){
if(ans[i][j])cout<<i<<" "<<j<<endl;
}
}
ans是记录被用掉的方块
先构造出一个正方形，
为什么是正方形呢，因为构造成正方形的话，是所有图像中，出现边最多的（注意到
那么这个正方形到底是多大的呢，假设这个正方形的边长是l，那么就是这个l就是要满足
ll<=n,并且（l+1）(l+1)>n,那么这个l就是我们初始的正方形的边长1
2
3
4
5
6int l=0,r=n;
while(l<r){
int mid=(l+r+1)/2;
if(2*(mid-1)*mid<=k)l=mid;
else r=mid-1;
}
分类讨论
首先，是剩下的边的要求是奇数个，这个奇数个还要分类讨论，这里详细解释下
1由下图可知，当只用下面的那一行的话，就可以满足奇数，一旦用到竖着的那一列，就会变成偶数，所以，如果是奇数的话，就要考虑只用下面那一行是不是够用
第一种情况：不够用
如果不够用的话，就要把它变成偶数，这样就可以套下面那个偶数的方法1
2
3
4
5if(k%2==1&&k>2*l-1){
ans[0][1]=1;
n--;
k--;
}
第二种情况：够用
够用的话：就把下面那行填，填到不能填位置1
2
3
4
5
6
7
8
9
10
11
12else{//如果是奇数的话,而且这个时候下面一行就可以填完了
ans[l+1][1]=1;
n--;
k--;
int x=l;
while(x>0&&k>0){
ans[l+1][x]=1;
n--;
x--;
k-=2;
}
}
2如果是偶数情况1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92if(k%2==0){//如果是偶数的话
ans[l+1][l+1]=1;//对角那个地方先来一个，这个不会有任何贡献
int x=l;
n--;
while(x>0&&k>0){
ans[x][l+1]=1;
n--;
x--;
k-=2;
}
x=l;
while(x>0&&k>0){
ans[l+1][x]=1;
n--;
x--;
k-=2;
}
}
```cpp
##完整代码
```cpp
void solve() {
int n,k;cin>>n>>k;
int l=0,r=n;
while(l<r){
int mid=(l+r+1)/2;
if(2*(mid-1)*mid<=k)l=mid;
else r=mid-1;
}
if(l*l>n){
cout<<"No"<<endl;
return ;
}
n-=l*l;
k-=2*(l-1)*l;
vector<vector<int>>ans(l+10,vector<int>(l+10));
for(int i=1;i<=l;i++){
for(int j=1;j<=l;j++){
ans[i][j]=1;
}
}
if(k>0){
if(k%2==1&&k>2*l-1){
ans[0][1]=1;
n--;
k--;
}//如果是奇数的话
//就是下面那一行满了都不够的话，那就没办法了，因为如果用另外一列的话就一定是偶数了
if(k%2==0){//如果是偶数的话
ans[l+1][l+1]=1;//对角那个地方先来一个，这个不会有任何贡献
int x=l;
n--;
while(x>0&&k>0){
ans[x][l+1]=1;
n--;
x--;
k-=2;
}
x=l;
while(x>0&&k>0){
ans[l+1][x]=1;
n--;
x--;
k-=2;
}
}else{//如果是奇数的话,而且这个时候下面一行就可以填完了
ans[l+1][1]=1;
n--;
k--;
int x=l;
while(x>0&&k>0){
ans[l+1][x]=1;
n--;
x--;
k-=2;
}
}
}
if(n<0){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
for(int i=0;n>0;n--,i+=2){
cout<<1000000000LL<<" "<<i<<endl;
}
for(int i=0;i<=l+1;i++){
for(int j=0;j<=l+1;j++){
if(ans[i][j])cout<<i<<" "<<j<<endl;
}
}
}
}
