Roundgod and Milk Tea 贪心

这个题好像可以用一种类似与置换的贪心方法来做~

sum记为剩余奶茶，一开始sum等于奶茶和

ans记录已经喝的奶茶数

不用排序，我们就从前往后直接处理，考虑的是每一个班最多可以喝多少杯奶茶

就是从剩余的奶茶里边减去本班的奶茶数（不让喝自己的）

但是这时候我们贪心考虑之间已经喝的奶茶都是尽量优先喝的是该班

但是这个时候你就能知道，本班这些人能喝多少杯奶茶了~

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
const int dir[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};
typedef long long ll;
const ll inFF = 9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn = 1e6 + 5;struct node {ll num, tea;
} a[maxn];int main() {int t, n;cin >> t;while (t--){cin >> n;ll sum=0,ans=0,c,x;for (int i = 1; i <= n; i++){scanf("%lld %lld", &a[i].num, &a[i].tea);sum+=a[i].tea;}for(int i=1;i<=n;i++){c=sum-(max(0LL,a[i].tea-ans));//可以喝的奶茶,就是这个x=min(c,a[i].num);//本班最多喝多少sum-=x;ans+=x;}printf("%lld\n",ans);}return 0;
}

 

总结

以上是生活随笔为你收集整理的Roundgod and Milk Tea 贪心的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。