筱玛爱历史

筱玛是一个热爱历史的好筱玛。在历史课中，筱玛最喜欢的内容是分封制的确立：

“普天之下，莫非王土；率土之滨，莫非王臣。”

史学家钱穆说：“周人封建，亦由当时形势之实际需要逐步逼桚而成。”

武王立国后，面对两个主要问题：一是如何防止殷商残余势力再起；二是周人势力偏于西部，如何有效地管治东部一大片土地和人民。武王于是在商末封建制的基础上，推行第一次分封。

西周时期的分封制认为，周王是全国最高统治者，是诸侯们更是天下人的共同主子。诸侯及其属民都是周王的臣属，必须服从于周王的命令。

分封制的产生，确立了周王的权威，开发了边远地区，使西周成为对周围民族具有较大影响的国家。

现在有 $n(n+1)$ 个人想要分封诸侯，但是为了捍卫武王的至尊权威，最多只能建立 $2n$ 个诸侯国。因此，周武王让这些人排成一排，从这些人中移去 $n(n-1)$ 名，使得剩下的人数刚好为 $2n$ 。

每个人都有一个威望，且不同人的威望各不相同。为了避免某个诸侯国国力过于强大而发生叛乱，动摇自己的统治地位，武王想要使各诸侯国的国力能够互相牵制，让剩下的人满足：威望最高的与威望次高的人相邻，威望第三高的与威望第四高的人相邻，……，威望次低的与威望最低的人相邻。

作为武王的亲信，为了不让武王发怒而遭杀身之祸，筱玛主动请缨，接下了这个难题。请你帮助筱玛，告诉武王是否存在这样的方案，若存在，则求出应该将哪些人留下。

#include<bits/stdc++.h> using namespace std; const int N=1e6+2005; struct node { int x,id; }a[N]; vector<int>ans; int flag[1005]; int vis[1005]; bool cmp(node a,node b) { return a.x<b.x; } int main() { int n,nn; scanf("%d",&n); nn=n; n=n*(n+1); for(int i=0;i<n;i++){ scanf("%d",&a[i].x); a[i].id=i; } sort(a,a+n,cmp); memset(flag,-1,sizeof flag); for(int i=0;i<n;i++) { int x=a[i].id; int bel=x/(nn+1); if(vis[bel]) continue; if(flag[bel]==-1){ flag[bel]=x; continue; } ans.push_back(x); ans.push_back(flag[bel]); vis[bel]=1; memset(flag,-1,sizeof flag); } for(auto it:ans) cout<<it+1<<' '; cout<<endl; return 0; }

#include<bits/stdc++.h> #define ll long long using namespace std; int n,m,i,j,x,v[1100001],aa[1100001],a[1100001]; int main(){ scanf("%d",&n); m=n*(n+1); for(i=1;i<=m;i++){ scanf("%d",&a[i]); aa[i]=a[i]; } sort(aa+1,aa+m+1); for(i=1;i<=m;i++)a[i]=lower_bound(aa+1,aa+m+1,a[i])-aa; for(i=1;i<=m;i++){ x=(a[i]-1)/(n+1)+1; if(v[x]==-1)continue; if(!v[x])v[x]=i; else{ printf("%d %d ",v[x],i); v[x]=-1; for(j=1;j<=n;j++)v[j]=min(v[j],0); } } }

详情