題目鏈接：點擊查看

題目大意：給出 n 個物品，每個物品有兩個屬性代表價值，有兩個玩家依次輪流拿物品，玩家一拿到物品后的貢獻為屬性一的累加，同理玩家二拿到物品后的貢獻為屬性二的累加，現(xiàn)在問兩人都希望在拿完物品后的貢獻比對方盡可能多，問兩人會如何選擇

題目分析：現(xiàn)在看來是一道很簡單的貪心問題，但是在比賽的時候卻沒有反應過來，可能是被那兩道簡單但是坑非常奇怪的題卡崩了心態(tài)吧，貪心策略就是將每個物品的屬性累加即可，因為當某個玩家選擇了這個物品后，其貢獻是相應的屬性，而其余的那個屬性則代表了對方拿不到這個物品所損失的代價，所以這個物品的貢獻是 a + b，同理，無論輪到哪個玩家拿取時，每個物品的貢獻都是 a + b ，所以按照這個值排序后，依次分配個兩個玩家就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;struct Node {int a,b,id;bool operator<(const Node& t)const{return a+b>t.a+t.b;} }a[N];int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); //#endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i].a);a[i].id=i;}for(int i=1;i<=n;i++)scanf("%d",&a[i].b);sort(a+1,a+1+n);vector<int>ans1,ans2;for(int i=1;i<=n;i++){if(i&1)ans1.push_back(a[i].id);elseans2.push_back(a[i].id);}for(int i=0;i<ans1.size();i++)printf("%d ",ans1[i]);printf("\n");for(int i=0;i<ans2.size();i++)printf("%d ",ans2[i]);printf("\n");return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 拿物品(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。