题目链接：点击查看

题目大意：给出两个长度为n的数列，现在要求选出n/2+1个位置，使得两个序列中这些位置的和分别大于各自序列之和的一半

题目分析：题意换句话说，是需要让我们从数组中选出一半，要大于另一半，这样我们可以以数组a为基准先从大到小排序，然后依次对于每两个相邻的b比较大小，选择较大的那个输出，因为此时数组a已经是降序排列的了，只需要让数组b满足条件就好了

比较让我惊艳到的是随机数的玄学做法，直接用STL里的random_shuffle函数将原序列随机排列，直到前n/2+1个数满足条件输出即可

代码：

排序：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int a,b,id;bool operator<(const Node& t)const{return a>t.a;} }q[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&q[i].a);q[i].id=i;}for(int i=1;i<=n;i++)scanf("%d",&q[i].b);sort(q+1,q+1+n);printf("%d\n",n/2+1);printf("%d ",q[1].id);for(int i=2;i<=n;i+=2){if(q[i].b>q[i+1].b)printf("%d ",q[i].id);elseprintf("%d ",q[i+1].id);}return 0; }

随机数：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int a,b,id; }q[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);LL suma=0,sumb=0;for(int i=1;i<=n;i++){scanf("%d",&q[i].a);suma+=q[i].a;q[i].id=i;}for(int i=1;i<=n;i++){scanf("%d",&q[i].b);sumb+=q[i].b;}while(1){random_shuffle(q+1,q+1+n);LL tempa=0,tempb=0;for(int i=1;i<=n/2+1;i++){tempa+=q[i].a;tempb+=q[i].b;}if(tempa*2>suma&&tempb*2>sumb){printf("%d\n",n/2+1);for(int i=1;i<=n/2+1;i++)printf("%d ",q[i].id);return 0;}}return 0; }

总结

以上是生活随笔为你收集整理的CodeForces - 798D Mike and distribution(构造+思维/玄学随机数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。