现在的位置: 首页 > 综合 > 正文

noi 2009 变换序列

2017年04月27日 ⁄ 综合 ⁄ 共 1470字 ⁄ 字号 评论关闭

O(n^2)算法:匈牙利暴力水过

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
//////////////////////////////////////////////////
int n;
int a[10001];
struct edge
{
   int v,next;
}e[20001];
int k;
int head[10001];

int pre[10001];
bool vis[10001];
//////////////////////////////////////////////////
void adde(int u,int v)
{
     e[k].v=v;e[k].next=head[u];head[u]=k++;
}
bool cmp(int a,int b){return a>b;}
bool hungary(int u)
{
     int v;
     for(int i=head[u];i!=-1;i=e[i].next)
     {
         v=e[i].v;
         if(vis[v]) continue;
         vis[v]=1;
         if(pre[v]==-1||hungary(pre[v]))
         {
             pre[v]=u;
             return 1;
         }
     }
     return 0;
}
//////////////////////////////////////////////////
void input()
{
     memset(head,-1,sizeof(head));
     memset(pre,-1,sizeof(pre));
     scanf("%d",&n);
     for(int i=0;i<n;i++) scanf("%d",&a[i]);
}
void solve()
{
     //init
     int a,b;
     int num[5];
     //calculate
     for(int i=0;i<n;i++)
     {
          a=::a[i];
          b=n-a;
          num[1]=i-a;
          num[2]=i+a;
          num[3]=i-b;
          num[4]=i+b;
          for(int j=1;j<=4;j++) if(num[j]<0||num[j]>=n)
          {
              num[j]=-n*2;
          }
          sort(&num[1],&num[5],cmp);
          adde(i,num[1]);//大 
          adde(i,num[2]);//小 
     }
     //output
     for(int i=n-1;i>=0;i--)
     {
          memset(vis,0,sizeof(vis));
          if(!hungary(i))
          {
              puts("No Answer");
              exit(0);
          }
     }
     int ans[10001];
     for(int i=0;i<n;i++) ans[pre[i]]=i;
     for(int i=0;i<n-1;i++) printf("%d ",ans[i]);
     printf("%d\n",ans[n-1]);
}
//////////////////////////////////////////////////
int main()
{
     #ifndef _TEST
     freopen("1562.in","r",stdin); freopen("1562.out","w",stdout);
     #endif
     input();
     solve();
     #ifdef _TEST
     for(;;);
     #endif
     return 0;
}

O(n)算法参考https://www.byvoid.com/blog/noi-2009-transform/

抱歉!评论已关闭.