HDU 5303 题意是在一个圆上，有n颗苹果树，相对起点的顺时针距离为xi，每棵树上有ai个苹果。现在带上一个容量为K的篮子，从起点出发，问将所有苹果收回来至少要花多少时间？ 显然，从起点出发，不论从从左或是右，在不跨过终点m时，摘到K个苹果后最佳的路径是原路返回。跨过了中点m，那么最佳路径是走一圈回到起点。显然，我们至多只会跨过m一次，因为跨过中点是不得已为之，走一圈是最长路径。 那么摘苹果就分成了三种情况，顺时针不过m采摘，逆时针不过m采摘，跨m采摘(至多一次)。预处理出单侧不跨m采摘的花费。 ldp记录采摘起点到顺时针的第i个苹果所需要的花费，那么 ldp[i]=ldp[i-K]+lcost[i]。 rdp记录采摘起点到逆时针的第i个苹果所需要的花费，那么 rdp[i]=rdp[i-K]+rcost[i]。 我们再枚举，跨越m的那次采摘的采摘区间，那么显然我们要让这次采摘覆盖单侧采摘中花费最大的那些苹果，即离起点最远的那些苹果。 假设这次采摘，在左侧摘i个，那么右侧摘K-i个， total_cost就由(ldp[lmax]+rdp[rmax])*2变成了(ldp[lmax-i]+rdp[rmax-(K-i)]）*2+L。枚举过程中取最小值即可。
//#include<bits/stdc++.h> #pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> #define LS (root<<1) #define RS ((root<<1)|1) #define LSON LS,l,mid #define RSON RS,(mid+1),r #define MID mid=((l+r)/2) #define LL long long #define mm(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=3e4+5; const LL Inf=1e18; vector<LL> ldp, rdp; int main(){ int T, n; int L, K; int a, b; scanf("%d",&T); while(T--){ ldp.clear(); rdp.clear(); ldp.push_back(0); rdp.push_back(0); scanf("%d%d%d",&L, &n, &K); for(int i=0;i<n;i++){ scanf("%d%d",&a, &b); while(b--){ if(2*a<L) ldp.push_back(a); else rdp.push_back(L-a); } } sort(ldp.begin(),ldp.end()); sort(rdp.begin(),rdp.end()); for(int i=K;i<ldp.size();i++) ldp[i]+=ldp[i-K];//把摘到i-K为止的cost累加到i上过 for(int i=K;i<rdp.size();i++) rdp[i]+=rdp[i-K]; LL ans=(ldp[(int)ldp.size()-1]+rdp[(int)rdp.size()-1])*2; for(int i=0;i<=K;i++){ a=max(0,(int)ldp.size()-1-i); b=max(0,(int)rdp.size()-1-(K-i)); LL tmp=(ldp[a]+rdp[b])*2; ans=min(ans,L+tmp); } printf("%lld\n",ans); } return 0; }