A. 奶牛飞车

贪心去搞就好了

const int N = 5e4 + 5;
int a[N];
int vis[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n , m ,  d , l;
	cin >> n >> m >> d >> l;
	for (int i = 1;i <= n ;i ++){
		cin >> a[i];
	}
	sort(a + 1 , a + n + 1);
	int tot = 1;
	int ans = 0;
	for (int i = 1; i <= n ; i ++){
		if (a[i] - (ans / m * d) >= l) ++ ans;
	}
	cout << ans << endl;
	return 0;
}

B. 牛奶规划

1.反悔贪心

vector<int> t[10005];
int tmx,n;
int ans;
priority_queue<int> q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		t[y].push_back(x);
		tmx=max(tmx,y);
	}
	for(int i=tmx;i>=1;i--){
		for(auto y:t[i]) q.push(y);
		if(q.empty()) continue;
		ans+=q.top();
		q.pop();
	}
	cout<<ans;
	return 0;
}

2.DP

struct _{
	int g,d;
	bool operator< (_ A){return d<A.d;}
}a[10010];
int n,dp[10010],s;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].g,&a[i].d);
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		for(int j=a[i].d-1;j>=1;j--){
			dp[j]=max(dp[j-1]+a[i].g,dp[j]);
			s=max(s,dp[j]);
		}
		dp[0]=max(dp[0],a[i].g);
		s=max(s,dp[0]);
	}
	printf("%d",s);
	return 0;
}

C. 集市班车

反悔贪心

#define pii pair<int,int>
using namespace std;
int n,k,c;
int s[50005],t[50005],m[50005];
vector<pii> a[10005];
int b[105];
int ans;
int main(){
	cin>>k>>n>>c;
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&s[i],&t[i],&m[i]);
		a[t[i]].push_back(make_pair(s[i],m[i]));
	}
	for(int i=1;i<=n;i++){
		for(int u=0;u<a[i].size();u++){
			pii x=a[i][u];
			for(int j=c;j&&x.second;j--){
				if(b[j]<=x.first){
					ans++;
					b[j]=i;
					x.second--;
				}
			}
			sort(b+1,b+c+1);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

D. 炸树

#define fi first
#define se second
#define pb push_back
using namespace std;

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int n, m, ans, ret, now;
int a[N], f[N], g[N];
vector<int> e[N];
void dfs(int u, int fa) {
	f[u] = iinf, g[u] = -iinf;
	for(auto v : e[u]) {
		if(v == fa) continue;
		dfs(v, u);
		f[u] = min(f[u], f[v] + 1);
		g[u] = max(g[u], g[v] + 1);
	}
	if(a[u] && f[u] > now) g[u] = max(g[u], 0);
	if(f[u] + g[u] <= now) g[u] = -iinf;
	if(g[u] == now) {
		ret++, f[u] = 0, g[u] = -iinf;
	}
}
bool check(int x) {
	ret = 0, now = x;
	dfs(1, 0);
	ret += (g[1] >= 0);
	return ret <= m;
} 
int main() { 
	cin >> n >> m;
	for(int i = 1; i <= n; i++)scanf("%d",&a[i]);

	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d",&u,&v); 
		e[u].pb(v), e[v].pb(u);
	}
	int l = 0, r = n;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n",ans);
	return 0;
}

E. 漫长的征途

反悔贪心加满油再放回来

pair <long long, long long> que[2000010];
int n, qhd = 1000005, qtl = 1000005, g, b, d;
pair <long long, long long> a[1000005];
long long ans = 0; 
inline bool Move(int dis) {
	while (qhd != qtl && dis) {
		if (que[qhd].second <= dis) {
			b -= que[qhd].second;
			dis -= que[qhd].second; ans += que[qhd].first * que[qhd].second;
			qhd++;
		} else {
			b -= dis;
			que[qhd].second -= dis; ans += dis * que[qhd].first;
			dis = 0;
		}
	}
	return dis == 0;
}
inline void PopGas(int cost) {
	while (qhd != qtl && que[qtl - 1].first >= cost) {
		b -= que[qtl - 1].second;
		qtl--;
	}
	que[qtl++] = make_pair(cost, g - b); b = g;
}
inline void Solve() {
	a[++n] = make_pair(d, 0);
	que[qtl++] = make_pair(0, b);
	for (int i = 1;i <= n;i++) {
		if (!Move(a[i].first - a[i - 1].first)) {
			puts("-1");
			return;
		}
		PopGas(a[i].second);
	}
	printf("%lld", ans);
}
int main() {
	cin>>n>>g>>b>>d;
	for (int i = 1;i <= n;i++) {
		scanf("%d %d",&a[i].first,&a[i].second);
	}
	sort(a + 1, a + n + 1);
	Solve();
	return 0;
}