网站开发的功能需求怎么写,移动互联网的长期趋势是,重庆网站服务建设,天台县城市建设规划局网站正题
题目链接:https://www.luogu.com.cn/problem/CF388C 题目大意
有nnn堆卡片#xff0c;第iii堆有sis_isi张#xff0c;给出每张卡的权值。现在先手选择一堆取走堆底的牌#xff0c;然后后手选择一堆取走堆顶的牌#xff0c;直到所有牌被取走。在双方都要求最大化取…正题
题目链接:https://www.luogu.com.cn/problem/CF388C 题目大意
有nnn堆卡片第iii堆有sis_isi张给出每张卡的权值。现在先手选择一堆取走堆底的牌然后后手选择一堆取走堆顶的牌直到所有牌被取走。在双方都要求最大化取走的牌的权值的情况下求先后手的权值。
1≤n,si≤100,1≤ai,j≤10001\leq n,s_i\leq 100,1\leq a_{i,j}\leq 10001≤n,si≤100,1≤ai,j≤1000 解题思路
大胆猜测结论是每堆牌都是先后手各自取走约一半的牌因为如果总和固定最大化自己就相当于最小化对方。
如果存在一种情况后手和先手各自取不同的堆那么这肯定是对后手优的又因为权值一样也就是对先手劣的与对先手和后手都优冲突。
现在偶数个数的都是平分的主要考虑奇数对于奇数来说就是先手取走中间那个然后交换先后手。
直接把奇数两边的平分然后拿中间出来排序先后手依次取走即可。
时间复杂度O(ns)O(ns)O(ns) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N110;
int n,s,sum,ans,m,a[N],r[N];
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,s);for(int j1;js;j)scanf(%d,a[j]),suma[j];if(s1){m;for(int j1;js/2;j)ansa[j];for(int js/22;js;j)ans-a[j];r[m]a[s/21];}else{for(int j1;js/2;j)ansa[j];for(int js/21;js;j)ans-a[j];}}sort(r1,r1m);reverse(r1,r1m);for(int i1;im;i)if(i1)ansr[i];else ans-r[i];printf(%d %d\n,int(sum/2.0ans/2.0),int(sum/2.0-ans/2.0));return 0;
}
