1010题 Bragging Dice
题目大意
二人的桶里各有五个骰子，二人轮流选择并进行一个操作：1.宣布一个可能存在的且比对方宣布的点数大或数量多的情况，2.挑战对方的情况。若捅里的骰子五个都一样则视为没有。
思路
当且仅当骰子都一样时后者赢
代码
#include <iostream>
#include <string.h>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int cup[3][7], sum[7];
int main() {
int t;
cin >> t;
while (t--) {
memset(cup, 0, sizeof(cup));
memset(sum, 0, sizeof(sum));
int n;
scanf("%d", &n);
for (int j = 1; j <= 2; j++) {
for (int i = 0; i < n; i++) {
int temp;
scanf("%d", &temp);
cup[j][temp]++;
sum[temp]++;
}
}
bool if3[3] = { 0 }; //是否符合规则3
if (n <= 6) {
for (int i = 1; i <= 2; i++) {
bool flag = 1;
for (int j = 1; j <= 6; j++) {
if (cup[i][j] > 1) {
flag = 0;
break;
}
}
if (flag) if3[i] = 1;
}
}
if (if3[1] && if3[2]) {
cout << "Just a game of chance." << endl;
continue;
}
else {
cout << "Win!" << endl;
continue;
}
//for (int i = 1; i <= 2; i++) {
// if (if3[i]) { //清零
// for (int j = 1; j <= 6; j++) {
// sum[j] -= cup[i][j];
// cup[i][j] = 0;
// }
// }
// else { //否则看是否符合规则2
// for (int j = 1; j <= 6; j++) {
// if (cup[i][j] == n) {
// cup[i][j]++;
// sum[j]++;
// break;
// }
// }
// }
//}
}
return 0;
}
1012题 Buy Figurines
题目大意
给定n个顾客和m个队伍，每个人有各自的到达时间与购买所需花费时间且每个人到达时会选择最短队伍排队，判断最终多久排完。
思路
遍历每位顾客，再循环遍历每个队伍，如果购买完了就弹出，如果弹出后没人则选择该队伍，若循环完后没有选择则选择人最少的队伍。
代码
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#pragma warning(disable:4996)
#define ll long long
using namespace std;
struct node {
ll l, r;
}peo[200005];
bool cmp(node a, node b) {
return a.l < b.l;
}
int main() {
int t, n, m, a, s;
cin >> t;
while (t--) {
scanf("%d %d", &n, &m);
vector<queue<node>> qs(m);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &a, &s);
peo[i].l = a;
peo[i].r = a + s;
}
sort(peo + 1, peo + 1 + n, cmp); //左端点递增排序
ll ans = 0;
for (int i = 1; i <= n; i++) { //遍历所有区间(顾客)
//最短队列的元素个数 最短队列下标
int minSize = n + 1, index = 0;
bool flag = 0;
for (int j = 0; j < m; j++) { //遍历所有m个队列
//更新队列，即弹出以消费完的顾客
while (!qs[j].empty() && peo[i].l >= qs[j].front().r) {
qs[j].pop();
}
//若当前队列没人排队，则可直接插入（因为必定为人最少且最靠前的队列）
if (qs[j].size() == 0) {
qs[j].push(peo[i]);
ans = max(ans, peo[i].r);
flag = 1;
break;
}
//否则更新minSize和index，找出最少人排队且尽量靠前的队列
if (qs[j].size() < minSize) {
minSize = qs[j].size();
index = j;
}
}
/*若当前peo[i]还没有插入，说明要插入的队列一定还有元素，
且要插入的元素紧跟队列最后*/
if (!flag) {
s = peo[i].r - peo[i].l;
peo[i].l = qs[index].back().r;
peo[i].r = peo[i].l + s;
qs[index].push(peo[i]);
ans = max(ans, peo[i].r);
}
}
cout << ans << endl;
}
return 0;
}