请问这个非要dp吗,这样贪心不可以吗
  • 板块CF730J Bottles
  • 楼主DaShabby
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/7/16 16:48
  • 上次更新2023/10/27 20:01:17
查看原帖
请问这个非要dp吗,这样贪心不可以吗
672837
DaShabby楼主2022/7/16 16:48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5e4+23,inf=0x3f3f3f3f;
ll dis[maxn][3],vis[maxn],idx,cnt;
struct node{
	int a,b,pos,c=0;
}bottle[109];
bool cmp1(struct node x,struct node y){
	return x.b>y.b;
}
bool cmp2(struct node x,struct node y){
	return x.pos<y.pos;
}
int main()
{
	int n,num=0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>bottle[i].a,idx+=bottle[i].a;
	for(int i=1;i<=n;i++)cin>>bottle[i].b,bottle[i].pos=i;
	sort(bottle+1,bottle+1+n,cmp1);
    for(int i=1;i<=n;i++){
    	if(idx>=bottle[i].b){
    		idx-=bottle[i].b;
    		num++;
    		bottle[i].c=bottle[i].b;
		}
		else if(idx){
			num++;bottle[i].c=idx;idx=0;
		}
	}
	//bottle[num].b+=idx;
//	for(int i=1;i<=num;i++)cout<<bottle[i].b<<' ';
//	cout<<endl;
	for(int i=1;i<=n;i++){
		 cnt+=max(bottle[i].a-bottle[i].c,bottle[i].c-bottle[i].a);
		//else cnt+=bottle[i].a;
	}
	cnt/=2;
	cout<<num<<' '<<cnt<<endl;
	return 0;
}
2022/7/16 16:48
加载中...