Description n件物品，每个物品有价值c[i]，两个人轮流拿，第一个人随便拿，第二个人只拿第一个没被拿的物品，第一个人想让自己拿到的物品总价值最大，输出他能拿到的最大价值和对方拿到物品的价值 Input 第一行一整数n表示物品数量，之后n个整数c[i]表示每件物品的价值(1<=n<=1e5,1<=a[i]<=1e9) Output 输出第一个人能拿到物品的最大价值以及第二个人拿到物品的价值 Sample Input 5 3 1 2 4 1 Sample Output 8 3 Solution 由于第一个人可以随便拿，那么不妨每次让其拿当前物品序列的第一个，开一个set存下第一个人拿的所有物品的数量，如果这次对方拿的物品价值大于set中元素最小值，说明第一个人在之前某一轮不应该拿第一个，而是应该拿这次对方拿的这个物品，那么就把set中最小元素删掉，把对方拿的这个物品加到set中表示拿这个物品，维护一个物品总价值即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111111 int n,a[maxn]; multiset<int>s; int main() { while(~scanf("%d",&n)) { s.clear(); ll sum=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i]; if(n%2)a[++n]=0; ll ans=0; for(int i=1;i<n;i+=2) { ans+=a[i]; s.insert(a[i]); if(a[i+1]>*s.begin()) { ans+=a[i+1]-*s.begin(); s.insert(a[i+1]); s.erase(s.begin()); } } printf("%I64d %I64d\n",ans,sum-ans); } return 0; }