#include<bits/stdc++.h> using namespace std; struct hh //创建结构体 { int a,id; }a[100020]; int n,zx[100020],v[100020],ans[100020],end1; bool cmp(hh x,hh y) { return x.a>y.a; } int main() { scanf("%d",&n); end1=n; for(int i=1;i<=n;i++) { int c; scanf("%d",&c); a[i].a=c;//大小 a[i].id=i;//位置 } sort(a+1,a+n+1,cmp);//按大小从大到小排序 for(int i=1;i<=n;i++) { zx[a[i].id]=i;//指向数组:记录id为x的是第i个数 } int t=0; for(int i=1;i<=n;i++) { if(v[a[i].id])//用过的点就不用了 continue; if(a[i].id==end1)//最后一个不能选 continue; ans[++t]=a[i].a;//选择了这一对卡片的第一个 v[a[i].id]=1;//标记 int lll=a[i].id+1; while(1)//找第二个点 { if(!v[lll]) { ans[++t]=a[zx[lll]].a; int llll=a[zx[lll]].id-1; if(a[zx[lll]].id==end1 )//如果第二个卡片是最后一个 while(1)//转移end1 { if(!v[llll]) { end1=llll; break; } else llll--; } v[lll]=1;//标记 break; } else lll++; } } if(n%2==1)//有奇数个卡片,剩下的直接放入目标序列 { for(int i=1;i<=n;i++) if(v[i]) { ans[++t]=a[i].a; break; } } for(int i=1;i<=n;i++) { printf("%d ",ans[i]); } return 0; }
时间: 2024-02-14 18:18:54 浏览: 26
这段代码是一个题目的解法,题目要求将一个序列分成若干个长度为 2 的子序列,并交换每个子序列的两个元素,使得交换后的序列的和最大。
代码中使用了结构体 hh 存储每个数的大小和位置,按大小从大到小排序,并记录每个位置所在的位置。然后从大到小遍历每个数,从未被选中的数中选择一个,找到其后面第一个未被选中的数,并将两个数的大小加入目标序列中。如果找到的第二个数已经被选中,则继续向后找,直到找到未被选中的数。如果第二个数是序列中的最后一个数,则将 end1 转移到该数的前一个未被选中的数上,并继续进行选择。
最后,如果原序列长度为奇数,则将最后一个未被选中的数加入目标序列中。
这段代码的时间复杂度为 O(nlogn),主要来自于排序操作。
相关问题
#include <bits/stdc++.h> using namespace std
这段代码是一个C++的头文件引用和命名空间的使用示例。具体来说,`#include <bits/stdc++.h>`是一个常用的头文件引用方式,它包含了C++标准库中的所有头文件。而`using namespace std`则是为了使用`std`命名空间中的标准库函数和对象,这样就可以直接使用`cout`、`cin`等标准输入输出流对象,而不需要写`std::cout`、`std::cin`。
这种写法虽然方便,但也存在一些问题。首先,包含了所有的标准库头文件可能会导致编译时间变长。其次,使用了`using namespace std`会将整个`std`命名空间中的所有标识符引入当前作用域,可能会导致命名冲突。因此,在实际开发中,建议根据需要只包含需要的头文件,并使用具体的命名空间来避免潜在的问题。
#include <bits/stdc++.h> using namespace std;
这个头文件是C++11标准引入的,它包含了所有标准库中的头文件。使用这个头文件可以方便地在一个地方包含所有需要的头文件,而不需要一个一个地包含。这个头文件通常只在竞赛中使用,因为它不是标准C++头文件,不保证在所有编译器中都能正常工作。
以下是一个使用这个头文件的示例,实现输入4个整数a、b、c、d,将它们倒序输出:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a << endl;
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)