NC25157. [USACO 2007 Feb G]Cow Sorting
描述
输入描述
第1行: 一个数, N。
第2~N+1行: 每行一个数,第i+1行是第i头牛的脾气值。
输出描述
第1行: 一个数,把所有牛排好序的最短时间。
示例1
输入:
3 2 3 1
输出:
7
Python3 解法, 执行用时: 971ms, 内存消耗: 6900K, 提交时间: 2023-08-17 09:28:32
''' 可以发现每头牛都有一个应该去的位置,假设把每个牛向应该去的位置连边, 会出现许多个环,每个环里的牛分别自身交换。 交换的方式有两种: 1.每个环里最小的那头牛让环里的其他牛都和他交换一次。 2.可能整个序列中的最小值比环里最小的要小很多, 那我们先让他俩交换,再用序列中的最小值和环里其他的牛交换一次,然后再交换回来。 ''' n = int(input()) dic = {} l = [] m = 0 for i in range(n): inp = int(input()) l.append((i+1, inp)) dic[i+1] = inp l.sort(key = lambda x:x[1]) mi = min(l, key = lambda x:x[1])[1] k1 = [] k2 = [] fil = [1 for i in range(n)] for i in range(n): k1.append(l[i][0]) dq0 = dq1 = 0 while (sum(fil) > 0): if (m == 0): i = 0 while (fil[i] == 0): i += 1 dq0 = k1[i] m = dq0 js = [m] fil[i] == 0 else: if (k1[m-1] == dq0): k2.append(js) fil[m-1] = 0 m = 0 else: fil[m-1] = 0 js.append(k1[m-1]) m = k1[m-1] su = 0 for i in k2: le = len(i) if (le == 1): pass elif (le == 2): su += dic[i[0]] + dic[i[1]] elif (le == 3): su += 2*dic[i[0]] + dic[i[1]] + dic[i[2]] else: if ((le-3) * dic[i[0]] > (le+1) * mi): su += (le+1) * mi + dic[i[0]] + sum([dic[j] for j in i]) else: su += (le-2) * dic[i[0]] + sum([dic[j] for j in i]) print(su)
C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 1416K, 提交时间: 2019-06-22 19:32:51
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=50000+20; ll a[N],vis[N]; ll least; map<ll,ll>m; ll solve(ll i) { ll j=m[a[i]]; ll minn=a[i]; vis[i]=1; ll x=0,num=a[i]; while(i!=j) { num+=a[j]; minn=min(minn,a[j]); vis[j]=1; x++; j=m[a[j]]; } //printf("x=%d,num=%d\n",x,num); return num+min(minn*(x-1),least*(x+2)+minn); } int main() { memset(vis, 0, sizeof(vis)); ll n,x; scanf("%lld",&n); for(ll i=1; i<=n; i++) { scanf("%lld",&a[i]); m[a[i]]=i; } sort(a+1,a+n+1); least=a[1]; ll ans=0; for(ll i=1; i<=n; i++) { if(!vis[i]) { ans+=solve(i); } } printf("%lld\n",ans); return 0; }
C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 744K, 提交时间: 2019-06-15 01:23:03
#include<bits/stdc++.h> using namespace std; const int M=1e5+10; int v[M],a[M],n,b[M],c[M]; int main(){ scanf("%d",&n); int ss=0x3f3f3f3f; for(int i=0;i<n;i++){ scanf("%d",&a[i]); c[i]=a[i]; ss=min(ss,a[i]); } sort(a,a+n); for(int i=0;i<n;i++) b[a[i]]=i; int ans=0; for(int i=0;i<n;i++){ int cur=i; int mm=0x3f3f3f3f; int tot=0; int sum=0; while(!v[cur]){ v[cur]=1; sum+=c[cur]; tot++; mm=min(c[cur],mm); cur=b[c[cur]]; } if(tot) ans+=min(sum+(tot-2)*mm,sum+mm+(tot+1)*ss); } printf("%d\n",ans); return 0; }