当前位置: 首页 > >

C. No More Inversions (构造)

发布时间:

C. No More Inversions

题意
思路
这个题刚开始看上去没有一点的思路,然后就想着找规律,自己写了一个暴力开始找规律。
找了很多组数据以后,慢慢的你会发现后面的对称部分每次都应该选择最大的选择,前面不对称的部分,应该就是从1开始递增,知道这个规律以后就很好写了。
暴力代码


#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 100;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair PII;
typedef pair PLL;
int a[100010];
int temp[100010];
long long ans;
void merge_sort(int l,int r)
{
if(l==r) return;

int mid=l+((r-l)>>1);
merge_sort(l,mid);
merge_sort(mid+1,r);

for(int i=l;i<=r;++i) temp[i]=a[i];

int i1=l,i2=mid+1;
for(int i=l;i<=r;++i)
{
if(i1>mid) a[i]=temp[i2++];
else if(i2>r) a[i]=temp[i1++];
else if(temp[i1]<=temp[i2]) a[i]=temp[i1++];
//左半边i1之后的元素都比i2大
else if(temp[i1]>temp[i2]){ans+=mid-i1+1;a[i]=temp[i2++];}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
int c[N],p[N];
cin>>n>>k;
int flag=0;
int cnt=0;
for(int i=1 ; i<=n ; i++)
{
if(!flag) cnt++;
else cnt--;
c[i]=cnt;
if(cnt==k) flag=1;
}
for(int i=1 ; i<=k ; i++) p[i]=i;
do
{
ans=0;
for(int i=1 ; i<=n ; i++)
{
cout< a[i]=p[c[i]];
}
merge_sort(1,n);
cout< }while(next_permutation(p+1,p+1+k));
}
return 0;
}


AC代码


#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair PII;
typedef pair PLL;
int n,k;
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1;i<=n-2*n-2*k+1;i++) cout << i << " ";
for(int i=k;i>n-2*n-2*k+1;i--) cout << i << " ";
cout << endl;
}
}


总结
当时并没有写出来,一般遇到不会的题就应该打表找一下规律,那样可以有效的帮助自己更好的解决问题。



友情链接: