首页 > 代码库 > uva1315 Crazy tea party(找规律)

uva1315 Crazy tea party(找规律)

题意就是说把顺时针排的1到n换成逆时针排的需要的最少交换步数。

如果是线形的一串数,需要的交换次数就是个冒泡排序的交换次数:n*(n-1)/2,或者用a[i]=(i-1)+a[i-1]推出来。

对于环形,切成两个线形就行了,通过观察规律知:越接近平均切开越好。

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst double eps=1e-10;const int INF=1000000000;const int maxn=32767+10;int T,n,ans,a[maxn];int main(){    //freopen("in1.txt","r",stdin);    //freopen("out.txt","w",stdout);    a[0]=a[1]=0;    for(int i=2;i<maxn;i++)    {        a[i]=(i-1)+a[i-1];    }    cin>>T;    while(T--)    {        scanf("%d",&n);        if(n==3) cout<<1<<endl;        else if(n==1||n==2) cout<<0<<endl;        else        {            ans=a[n/2]+a[(n-n/2)/2];            cout<<ans<<endl;        }    }    //fclose(stdin);    //fclose(stdout);    return 0;}

 

uva1315 Crazy tea party(找规律)