http://www.spoj.pl/problems/MUSIC/
USACO不知那年那月的月赛题。。。
看上去很BT。。但如果看一下部分和的话。。
会发现搞那么多也就是交换Sx-1于Sy。。
要让条件满足。。必须要把部分和顺序排序。。并且S1>0以及没有相同的部分和。。
那么最小交换数就是n-轮换数。。很好求。。
Code。。。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
const int maxn=100000;
using namespace std;
int S[maxn],P[maxn],n;
bool cmp(const int&x,const int&y)
{
return S[x]<S[y];
}
void Judge()
{
if(S[P[0]]<=0)
cout<<-1<<endl,exit(0);
for(int i=1;i<n;i++)
if(S[P[i]]==S[P[i-1]])
cout<<-1<<endl,exit(0);
}
void init()
{
scanf("%d",&n);
scanf("%d",S);P[0]=0;
for(int i=1;i<n;i++)
{
scanf("%d",S+i);
S[i]+=S[i-1];
P[i]=i;
}
sort(P,P+n,cmp);
Judge();
}
void solve()
{
bool mark[maxn]={0};int ans=n;
for(int i=0;i<n;i++) if(!mark[i])
{
int t=i;
while(!mark[t])
mark[t]=true,t=P[t];
ans–;
}
cout<<ans<<endl;
}
int main()
{
init();
solve();
}