题目链接:
题意:
有n架飞机要起飞,起飞的时间是t1=k+1,t2=k+2...tn=k+n。
现在有n个位置,每个位置的cost为(t-i)*ai(t>=i),现在问你如何给每架飞机安排位置,使得sumcost最小。
题解:
考虑贪心,先将ai 从大到小排序,显然对于大的a,乘的数越小越好,然后用set搞一搞就行了。
1 #include2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 typedef long long ll; 5 typedef pair P; 6 7 const int N=3e5+7; 8 multiset st; 9 int n,k,ans[N];10 P a[N];11 ll ret=0;12 int main(){13 scanf("%d%d",&n,&k);14 F(i,1,n)scanf("%d",&a[i].first),a[i].second=i;15 sort(a+1,a+1+n,greater ());16 F(i,1,n)st.insert(k+i);17 F(i,1,n)18 {19 auto it=st.lower_bound(a[i].second);20 ans[a[i].second]=*it;21 ret+=(ll)(*it-a[i].second)*a[i].first;22 st.erase(it);23 }24 printf("%lld\n",ret);25 F(i,1,n)printf("%d%c",ans[i]," \n"[i==n]);26 return 0;27 }