Codeforces 3B Lorry
程序员文章站
2022-03-02 23:24:59
...
很有意思的贪心题。
有两种东西,一个消耗2,一个消耗1,各自有自己的属性val,开始有v可以消耗,问怎么消耗val最大。
设数组a存放消耗为1的,数组b存放消耗为2的。
一开始想的贪心策略是:先对数组a和b从大到小排序,每次比较数组a中的2个(如果有两个的话)和b中的一个哪个大,更新答案,最后特殊处理一下a只剩1个的情况。但是这样有一个问题:比如a中元素是5,3,3,b中元素是7,,v=3。按照最初的思路程序是先取5和3,v-2变成1,再取3,最终结果是11。但是如果取7和5的话会得到12。所以思路错误。
正确思路是先把消耗为2的都放进答案里面,然后放消耗为1的(如果有剩余的空间),然后维护答案,比较a中最大的两个和b中最小的那一个,需要强调的是,不用考虑a中的一个元素的值比b中的元素的值大的情况(想一想,为什么)。最后处理一下边界情况就AC啦啦啦----
#include <bits/stdc++.h>
using namespace std;
struct node{
int val ;
int id;
}a[101010],b[101010];
int v,n,num1,num2,t1,t2,pos1,pos2,f,tot;
set<int> ans;
int cmp(const node & c ,const node & d){
return c.val>d.val;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>v;
for(int i = 1;i<=n;i++){
cin>>t1>>t2;
if(t1==1) a[num1++] = {t2,i};
else b[num2++] = {t2,i};
}
sort(a,a+num1,cmp);
sort(b,b+num2,cmp);
for(pos2;pos2<num2&&v>1;pos2++) {
ans.insert(b[pos2].id);
tot += b[pos2].val;
v -= 2;
}
for(pos1;pos1<num1&&v>0;pos1++){
ans.insert(a[pos1].id);
tot += a[pos1].val;
v--;
}
for(pos2--;pos2>=0;pos2--){
if(pos1>=num1) break;
if(pos1<num1-1) {
if(a[pos1].val+a[pos1+1].val>b[pos2].val) {
tot += (a[pos1].val+a[pos1+1].val - b[pos2].val);
ans.erase(b[pos2].id);
ans.insert(a[pos1].id);ans.insert(a[pos1+1].id);
pos1 += 2;
}
else break;
}
else if(a[pos1].val>b[pos2].val){
tot += (a[pos1].val-b[pos2].val);
ans.erase(b[pos2].id);
ans.insert(a[pos1].id);
pos1++;
}
}
cout<<tot<<endl;
for(set<int>::iterator it = ans.begin();it!=ans.end();it++)
cout<<*it<<' ';
return 0;
}
上一篇: 智联招聘 爬虫职位信息的爬取
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
『ACM C++』 Codeforces | 1066B - Heaters
-
『ACM C++』 Codeforces | 1003C - Intense Heat
-
Codeforces 939A题,B题(水题)
-
树莓派3B的WiFi中文乱码问题无法连接_解决方案:
-
CodeForces 29D Ant on the Tree
-
Codeforces Global Round 9-C. Element Extermination
-
codeforces 712B Memory and Trident
-
CodeForces 962D Merge Equals
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion