网站建设合同定义,手机网站logo,网站取消301后,h5制作软件 知乎 推荐文章目录 一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 一、题目
1、原题链接 4965. 三国游戏 2、题目描述 二、解题报告
1、思路分析 思路参考y总#xff1a;y总讲解视频 #xff08;1#xff09;题目中的获胜情况分为三种#xff… 文章目录 一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 一、题目
1、原题链接 4965. 三国游戏 2、题目描述 二、解题报告
1、思路分析 思路参考y总y总讲解视频 1题目中的获胜情况分为三种魏国胜兵量为X、蜀国胜兵量为Y、吴国胜兵量为Z。以魏国胜为例需要使得XYZ也就是需要使得X-Y-Z0记WX-Y-Z即W0W初始为0因为X、Y、Z初始均为0。 2由于每个事件都会使XYZ分别增加A[i]、B[i]、C[i]。记V[i]A[i]-B[i]-C[i]即每个事件会使W增加V[i]。所以题目就可以转化为最多多少个事件也就是对W加最多多少次不同的V[i]可以使W保持大于0也就是这些事件的每个V[i]之和大于0。 3可以将V数组进行从大到小排序由于W初始为0所以当发生V[i]0的事件发生最多的情况下发生的事件最多的情况为最优解。所以大到小依次枚举V[i]并同时记录当前发生事件数和到目前枚举到的V[i]之和若出现总和不大于0时说明此时已经不是最优解最优解即为除去当前事件前面所有事件均发生的情况。 4依据相同思路依次求出蜀国、吴国获胜时的最大发生事件数取最大值即可若不存在让任何一国获胜的情况按题目要求输出即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include iostream
#include algorithm
using namespace std;
const int N 100010;
int n;
int a[N], b[N], c[N];
int v[N];
bool cmp(int A ,int B) {return A B;
}
//x[]为获胜国的事件产生效果y[]、z[]为未获胜国的
int solve(int x[], int y[], int z[]) {for (int i 0; i n; i) {v[i] x[i] - y[i] - z[i];}sort(v, v n, cmp);//注可能会超intlong long sum 0, cnt 0; //sum记录当前枚举到V[i]的总和,cnt记录发生事件数for (int i 0; i n; i) {sum v[i];if (sum 0) cnt;else break;} return cnt;
}
int main() {cin n;for (int i 0; i n; i) cin a[i];for (int i 0; i n; i) cin b[i];for (int i 0; i n; i) cin c[i];int res 0;int num1 solve(a, b, c);int num2 solve(b, a, c);int num3 solve(c, a, b);//取三种情况最大值res max(max(num1, num2), num3);if (res) cout res;else cout -1; //若不存在则输出-1return 0;
}
