比赛链接：https://www.nowcoder.com/activity/2018codem/index?from=meituan
1、下单
给定若干商品，可以选择打折、满减两种方式。
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
struct Manjian {
int x, y;
};
const int N = 107;
const int M = 1007;
int price[N];
int can[N];
Manjian manjian[M];
int n, m;
int main() {
// freopen("in.txt", "r", stdin);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> price[i] >> can[i];
}
for (int i = 0; i < m; i++) {
cin >> manjian[i].x >> manjian[i].y;
}
double useZheco = 0;
for (int i = 0; i < n; i++) {
if (can[i]) {
useZheco += 0.8 * price[i];
}else{
useZheco+=price[i];
}
}
double jian = 0xfffffff;
double s = 0;
for (int i = 0; i < n; i++) s += price[i];
for (int i = 0; i < m; i++) {
if (manjian[i].x <= s) {
jian = min(s - manjian[i].y, jian);
}
}
double ans = min(jian, useZheco);
printf("%.2f\n",ans);
return 0;
}
2、买可乐
此题看上去可乐可以买多种，实际上只能买一种。因为每种可乐都是不限数量的，如果限制数量那也很简单，也是一个排序问题。
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN=1e4+7;
int n,m,k;
int a[MAXN],b[MAXN];
int buy[MAXN];
double good(int x){
return a[x]*m+b[x]*(n-m);
}
int main() {
//freopen("in.txt", "r", stdin);
cin>>n>>m>>k;
int ans=0;
for(int i=0;i<k;i++){
cin>>a[i]>>b[i];
}
for(int i=0;i<k;i++){
if(good(i)>=good(ans)){
ans=i;
}
}
buy[ans]=n;
cout<<buy[0];
for(int i=1;i<k;i++){
cout<<" "<<buy[i];
}
cout<<endl;
return 0;
}
3、世界杯足球赛
16支球队组成一颗4层的二叉树，求每支球队到达根的概率。
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 1e4 + 7;
double a[17][17];
struct Node {
double a[17];
};
Node b[100];
void solve(int x) {
for (int i = 0; i < 16; i++) b[x].a[i] = 0;
if (x >= 16) {
b[x].a[x - 16] = 1;
} else {
solve(x << 1);
solve((x << 1) | 1);
for (int i = 0; i < 16; i++) {
for (int j = 0; j < 16; j++) {
b[x].a[i] += a[i][j] * b[x << 1].a[i] * b[x << 1 | 1].a[j];
b[x].a[j] += a[j][i] * b[x << 1].a[i] * b[x << 1 | 1].a[j];
}
}
}
//cout<<x<<endl;
//cout<<"======"<<endl;
//for(int i=0;i<16;i++)cout<<" "<<b[x].a[i];
//cout<<endl;
}
int main() {
// freopen("in.txt", "r", stdin);
for (int i = 0; i < 16; i++) {
for (int j = 0; j < 16; j++) {
cin >> a[i][j];
}
}
solve(1);
cout << b[1].a[0];
for (int i = 0; i < 16; i++) {
cout << " " << b[1].a[i];
}
cout << endl;
return 0;
}
4、MedoC资格赛
这道题坑有不少，如果实在不知道哪里错了，重写一遍。
人脑读代码时总是有一种惰性，因此无法发现隐含的bug。人读代码时，容易被代码牵着思路走。
而写代码时，人脑是主动输出的。
这道题注意点如下：
- 每轮比赛的权值不能出现浮点，出现浮点后可能会造成结果不精确。实际上，这道题的权值使用long就能够存下了。第i轮资格赛更新后的权值为$w_i^'=prod/roundMax_i\prodw_i$
- 排名并列就是不确定能否出线，如果第k+1名的成绩不等于第k名，那么这些并列第k名的都是稳赢。
- 胜负和的判断
在任何情形下都胜利的人就是胜利；
在任何情形下都失败的人就是失败；
其余情况，就是不太确定的情况。 - 需要分两种情况考虑，有没有不确定量
如果存在-1，那么需要枚举这个人所能够取得的一切成绩
如果不存在-1，那么只需要考虑当前情况即可
这道题只有一个-1，真的是已经非常友好了。 - 只看首尾是错误的
比如C的取值为50,那么只看C=0和C=50两种情况是不够的，结果是错误的。
因为C的取值可能影响比赛各个轮次的权重，从而影响每个人的成绩。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
int n, m, k, C;
final int MAX_N = 507;
final int MAX_M = 7;
int w[] = new int[MAX_M];
long a[][] = new long[MAX_N][MAX_M];
int res[][] = new int[MAX_N][MAX_N];//每轮是否能够胜出
final int WIN = 1, LOSE = 2, PEACE = 3;
class Pair {
int ind;
long value;
Pair(int ind, long value) {
this.ind = ind;
this.value = value;
}
@Override
public String toString() {
return String.format("%d %d", ind, value);
}
}
void solve(int[] res) {
long[] we = new long[MAX_M];
long[] ma = new long[MAX_M];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ma[j] = Math.max(ma[j], a[i][j]);
long prod = 1;
for (int i = 0; i < m; i++)
if (ma[i] > 0)
prod *= ma[i];
for (int i = 0; i < m; i++)
if (ma[i] > 0) we[i] = prod / ma[i] * w[i];
else we[i] = 0;
long[] score = new long[MAX_N];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (ma[j] > 0)
score[i] += we[j] * a[i][j];
Pair pairs[] = new Pair[MAX_N];
for (int i = 0; i < n; i++) pairs[i] = new Pair(i, score[i]);
Arrays.sort(pairs, 0, n, (o1, o2) -> {
if (o1.value < o2.value) return 1;
else if (o1.value == o2.value) return 0;
else return -1;
});
int unsureBeg = k - 1, unsureEnd = k - 1;
while (unsureBeg >= 0 && pairs[unsureBeg].value == pairs[k - 1].value) unsureBeg--;
while (unsureEnd < n && pairs[unsureEnd].value == pairs[k - 1].value) unsureEnd++;
if (unsureEnd == k) unsureBeg = k - 1;
for (int i = 0; i <= unsureBeg; i++) res[pairs[i].ind] = WIN;
for (int i = unsureBeg + 1; i < unsureEnd; i++) res[pairs[i].ind] = PEACE;
for (int i = unsureEnd; i < n; i++) res[pairs[i].ind] = LOSE;
// for (int i = 0; i < n; i++) {
// System.out.println(pairs[i]);
// }
// for (int i = 0; i < n; i++) {
// System.out.print(res[i] + " ");
// }
// System.out.println("==============");
}
boolean all(int x, int y) {
for (int j = 0; j <= C; j++)
if (res[j][x] != y)
return false;
return true;
}
Main() {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
k = cin.nextInt();
C = cin.nextInt();
for (int i = 0; i < m; i++) w[i] = cin.nextInt();
int badX = -1, badY = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = cin.nextInt();
if (a[i][j] == -1) {
badX = i;
badY = j;
}
}
}
if (badX == -1) {
solve(res[0]);
for (int i = 0; i < n; i++) {
System.out.println(res[0][i]);
}
} else {
for (int i = 0; i <= C; i++) {
a[badX][badY] = i;
solve(res[i]);
}
for (int i = 0; i < n; i++) {
if (all(i, WIN)) {
System.out.println(WIN);
} else if (all(i, LOSE)) {
System.out.println(LOSE);
} else {
System.out.println(PEACE);
}
}
}
cin.close();
}
public static void main(String[] args) {
new Main();
}
}
5、万无一失的旅行方案
这道题对了一半。
要保证最优路径中的每一站都能换乘，其实能否换乘是由城市决定的，一个城市有一个最晚出发时间，大于最晚出发时间的车次是无论如何不能订票的，因为大于最晚出发时间的车次是用来改签的。
首先，从n号结点出发用队列搜索一遍，初始化每个城市的最晚出发时间；
然后，从n号结点出发用队列搜索一遍，求dp[城市][出发时间]
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN =507;//最大结点数
const int MAXM = 15007;//最大边数
const int MAXTIME = 49;//最大时间
struct Edge {
int x, y,c,ts,td;//出发地，目的地，花费，出发时间，到达时间
};
Edge g[MAXN][MAXM];//g[i][j]表示到达结点i的第j条边
int startTime[MAXN];//每个结点的最晚出发时间（可以去等号），晚于此时间没有备选方案
int len[MAXN]; //len[i]表示到达结点i的边数
int n,m; //n个结点，m条边
int dp[MAXN][MAXTIME];//动态规划，dp[i][j]表示在j时间出发，从城市i到达n所需要的最少花费
const int MAXCOST = 1007 * MAXM;//花费的上界
//自定义队列
struct Queue {
int a[MAXN];
bool inq[MAXN];//每个元素只进队列一次
int head = 0;
int tail = 0;
void init() {
head = 0;
tail = 0;
for (int i = 0; i < MAXN; i++)inq[i] = false;
}
void enq(int x) {
if (inq[x]) return;
a[tail] = x;
inq[x] = 1;
tail = (tail + 1) % MAXN;
}
int deq() {
int ans = a[head];
head = (head + 1) % MAXN;
inq[ans] = 0;
return ans;
}
bool empty() {
return head == tail;
}
}q;
void showEdge(Edge &e) {
printf("%d(%d)-%d->%d(%d) ", e.x, e.ts, e.c, e.y, e.td);
}
void showNode(int city) {
cout << "city " << city << " startTime " << startTime[city] << endl;
for (int i = 0; i < len[city]; i++) {
if (g[city][i].ts > startTime[g[city][i].x]) {
cout << " [start late] ";
}
showEdge(g[city][i]);
if (g[city][i].td > startTime[city] - 1) {
cout << " [reach late] ";
}
}
puts("");
}
void showGraph() {
for (int i = 1; i <= n; i++) {
showNode(i);
}
puts("================");
}
//计算从每个城市出发的最晚时间
void cutEdges() {
//每个城市的出发时间
for (int i = 0; i < n; i++) {
startTime[i] = -1;//出发时间初始化为尽量小
}
//目的结点入队
startTime[n] = MAXTIME;
q.init();
q.enq(n);
while (!q.empty()) {
int now=q.deq();
for (int i = 0; i < len[now]; i++) {
Edge* e = &g[now][i];
if (e->td < startTime[e->y]-1) {//到达时间必须早于目的地的出发时间
int ts = e->ts - 1;//-1表示留下改签的时间
if (startTime[e->x] < ts) {
q.enq(e->x);
startTime[e->x] = ts;
}
}
}
}
}
void update(int city, int startTime, int cost) {
for (int i = 0; i <= startTime; i++) {
dp[city][i] = min(dp[city][i], cost);
}
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j <= MAXTIME; j++) {
dp[i][j] = MAXCOST;
}
}
for (int i = 0; i <= MAXTIME; i++)dp[n][i] = 0;
q.init();
q.enq(n);
while (!q.empty()) {
int now = q.deq();
for (int i = 0; i < len[now]; i++) {
Edge*e = &g[now][i];
//如果到达时间太晚，直接跳出
if (e->td >= startTime[e->y]) break;
//如果出发时间太晚，继续循环
if (e->ts > startTime[e->x])continue;
int co = e->c + dp[e->y][e->td+1];
if (co < dp[e->x][e->ts]) {
update(e->x, e->ts, co);
q.enq(e->x);
}
}
}
}
int comp(const void *x,const void *y) {
Edge *xx = (Edge*)x;
Edge *yy = (Edge *)y;
return xx->td-yy->td;
}
void sortEdges() {
for (int i = 1; i <= n; i++) {
qsort(g[i], len[i], sizeof(Edge), comp);
}
}
void showDp() {
cout << "DP is:" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < MAXTIME; j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}
}
int main() {
freopen("in.txt", "r", stdin);
scanf("%d%d", &n,&m);
for (int i = 0; i < m; i++) {
int x,y,c ,h1, m1, h2, m2;
scanf("%d%d%d%d:%d%d:%d",&x,&y,&c,&h1,&m1,&h2,&m2);
Edge *e = &g[y][len[y]++];
e->x = x;
e->y = y;
e-> c = c;
e->ts = h1 << 1 | (m1==30?1:0);
e->td = h2 << 1 | (m2 == 30 ? 1 : 0);
}
sortEdges();
cutEdges();
solve();
int ans = MAXCOST;
for (int i = 0; i < MAXTIME; i++) {
ans = min(dp[1][i],ans);
}
if (ans == MAXCOST)ans = -1;
cout << ans << endl;
return 0;
}
编程时，多打印些东西，多写点注释，多重构或重写，就容易发现bug。