T638475 调酒大师

错误代码

#include<bits/stdc++.h>

using namespace std;

long long t, a, b;

int main(){
	cin >> t;
	while(t--){
		cin >> a >> b;
		if(a > b){
			swap(a, b);
		}
		if(a * 3 <= b){
			cout << a << '\n';
		}
		else{
			cout << a / 2 << '\n';
		}
	}
	return 0;
}

错误原因：公式推错了。

正确代码

#include<bits/stdc++.h>

using namespace std;

long long t, a, b;

int main(){
	cin >> t;
	while(t--){
		cin >> a >> b;
		cout << min((a + b) / 4, min(a, b)) << '\n';//(a + b) / 4 是最理想的的情况，而和 min(a, b) 取最小值则是因为如果a或b比最理想情况小则不是最小情况，而是a和b的最小值。
	}
	return 0;
}

思路：多枚举一些例子，然后推出公式。

T638471 小梦的su7

错误代码

#include<bits/stdc++.h>

using namespace std;

struct P{
	long long t, x;
}k[100005];

long long n, m, a[100005], b[100005], s, ans;
bool f[100005];
//priority_queue<long long, vector<long long>, greater<long long> >q;

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> k[i].x >> k[i].t;
		b[i] = a[k[i].t];
		f[k[i].t] = 1;
		//q.push({k[i].x, k[i].t});
	}
	for(int i = 1; i <= n; i++){
		if(f[i] == 0){
			s++;
			b[m + s] = a[i];
		}
	}
	s = 1;
	for(int i = 1; i <= m; i++){
		k[i].x -= k[i - 1].x;
		for(s = 1; s <= n; s++){
			if(b[s] >= k[i].x){
				b[s] -= k[i].x;
				k[i].x = 0;
				ans += k[i].x;
				break;
			}
			else{
				k[i].x -= b[s];
				b[s] = 0;
				ans += b[s];
			}
		}
		if(k[i].x != 0){
			break;
		}
		b[i] = a[k[i].t];
	}
	for(int i = 1; i <= n; i++){
		ans += b[i];
	}
	cout << ans;
	return 0;
}

错误代码：模拟出错了。

正确代码

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pos first
#define idx second
const int MOD = 1e9 + 7;
typedef long long ll;
using namespace std;
const int N = 2e5 + 5;

int a[N], x[N], t[N];//a代表现在的电量， x代表充电站离起点的距离，t代表充电站可以给t[i]电池充电。
int r[N];
queue<int> yxj[N + 1];

int main() {
	int n, m;
	cin >> n >> m;
	
	priority_queue<pii, vector<pii>, greater<pii> > s;
	}
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		r[i] = a[i];
	}
	
	for (int i = 1; i <= m; i++) {
		cin >> x[i] >> t[i];
		yxj[t[i]].push(x[i]);//将位置推入队列
	}
	
	for (int i = 1; i <= n; i++) {
		yxj[i].push(MOD);
	}
	
	for (int i = 1; i <= n; i++) {
		int pos = yxj[i].front();
		yxj[i].pop();
		s.push({pos, i});
	}
	
	int ans = 0 ;
	for (int i = 1; i <= m; i++) {
		int len = x[i] - x[i - 1];
		
		while (len > 0) {//模拟电池的消耗情况。
			if (s.empty())break;
			pii top = s.top();
			s.pop();
			
			if (a[top.idx] <= len) 
			{
				len -= a[top.idx];
				a[top.idx] = 0;
			} 
			else 
			{
				a[top.idx] -= len;
				len = 0;
				s.push(top);
				break;
			}
		}
		//更新
		if (len > 0)
		{
			ans += (x[i] - x[i - 1] - len);
			break;
		} 
		else
		{
			a[t[i]] = r[t[i]];
			
			
			int fi = yxj[t[i]].front();
			if(yxj[t[i]].size()) yxj[t[i]].pop();
			
			if(s.size() && s.top().idx == t[i]) s.pop();
			
			s.push({fi, t[i]});
			ans += x[i] - x[i - 1];
		}
	}
	
	
	for (int i = 1; i <= n; i++) {//最后的电量可能没有算进去。
		ans += a[i];
	}
	cout << ans << endl;
	return 0;
}

思路：模拟加贪心。