Ticket Hoarding（1400）

题目描述

思路描述

容易想到，本题要确保购买天数最少，设购买的天数为cnt，那么要在n天内挑选出门票最小的cnt天。当然，我们考虑，门票价格越小则购买越多，反之，门票价格越大则购买越少。

至于天数cnt，我们可知要购买k张门票，而每天最多只能购买m张票，所以cnt=(k+m-1)/m;

将门票价格先按价格排序挑出cnt天，然后将这cnt天按照输入时的顺序排序。用num记录买了多少张。如果当天价格不是cnt天中最大的，就买m张票，否则就买k%m，除非有多个最大门票价格。

#include<bits/stdc++.h> #define int long long using namespace std; struct node { int v,id; }; bool cmp1(node a,node b) { if(a.v==b.v) return a.id<b.id; return a.v<b.v; } bool cmp2(node a,node b) { return a.id<b.id; } void solve() { int n,m,k;cin>>n>>m>>k; vector<node>a(n); for(int i=0;i<n;i++) { cin>>a[i].v; a[i].id=i; } sort(a.begin(),a.end(),cmp1); int cnt=(k+m-1)/m; int c=k%m; vector<node>b(cnt); for(int i=0;i<cnt;i++) { b[i]=a[i]; } sort(b.begin(),b.end(),cmp2); int ans=0; int num=0; int f=0; for(int i=0;i<cnt;i++) { if(c&&!f&&b[i].v==a[cnt-1].v) { ans+=c*(b[i].v+num); num+=c; f=1; } else { ans+=m*(b[i].v+num); num+=m; } } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T;cin>>T; while(T--) { solve(); } return 0; }

谢谢观看！