ZOJ 2132 The Most Frequent Number (贪心)
The number 贪心 zoj most
2023-09-11 14:17:18 时间
题意:给定一个序列,里面有一个数字出现了超过 n / 2,问你是哪个数字,但是内存只有 1 M。
析:首先不能开数组,其实也是可以的了,后台数据没有那么大,每次申请内存就可以过了。正解应该是贪心,模拟一个栈,因为答案肯定出现次数比其他所有数字的出现次数还多,所以每次和栈顶的元素比较,如果相同,就放到栈里,否则删除栈顶元素,这样最后剩下的肯定是出现次数最多的元素,我们可以用两个变量来模拟这个栈。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <set> #include <queue> #include <algorithm> #include <vector> #include <map> #include <cctype> #include <cmath> #include <stack> #include <sstream> #include <list> #include <assert.h> #include <bitset> #include <numeric> #define debug() puts("++++") #define gcd(a, b) __gcd(a, b) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define fi first #define se second #define pb push_back #define sqr(x) ((x)*(x)) #define ms(a,b) memset(a, b, sizeof a) #define sz size() #define be begin() #define ed end() #define pu push_up #define pd push_down #define cl clear() #define lowbit(x) -x&x //#define all 1,n,1 #define FOR(i,n,x) for(int i = (x); i < (n); ++i) #define freopenr freopen("in.in", "r", stdin) #define freopenw freopen("out.out", "w", stdout) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const LL LNF = 1e17; const double inf = 1e20; const double PI = acos(-1.0); const double eps = 1e-10; const int maxn = 1e5 + 5; const int maxm = 700 + 10; const LL mod = 1000000007; const int dr[] = {-1, 1, 0, 0, 1, 1, -1, -1}; const int dc[] = {0, 0, 1, -1, 1, -1, 1, -1}; const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; int n, m; const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; inline bool is_in(int r, int c) { return r >= 0 && r < n && c >= 0 && c < m; } inline int readInt(){ int x; scanf("%d", &x); return x; } int main(){ while(scanf("%d", &n) == 1){ int cnt = 0, t = 0; for(int i = 0; i < n; ++i){ scanf("%d", &m); if(cnt == 0){ t = m; ++cnt; } else{ if(m == t) ++cnt; else --cnt; if(cnt < 0) cnt = 1, t = m; } } printf("%d\n", t); } return 0; }
相关文章
- poj 1027 Ignatius and the Princess II全排列
- Maven 错误 :The POM for com.xxx:jar:0.0.1-SNAPSHOT is invalid, transitive dependencies (if any) will not be available
- 【异常】The dependencies of some of the beans in the application context form a cycle
- [RxJS 6] The Catch and Rethrow RxJs Error Handling Strategy and the finalize Operator
- [TypeScript] The Basics of Generics in TypeScript
- [Angular2 Router] Optional Route Query Parameters - The queryParams Directive and the Query Parameters Observable
- DevOps - 【转】The 15-point DevOps Checklist
- [XState] Send Events to the Machine with the XState Send Action Creator
- [React] Use the Fragment Short Syntax in Create React App 2.0
- [Vue + TS] Watch for Changes in Vue Using the @Watch Decorator with TypeScript
- [Angular2 Router] Optional Route Query Parameters - The queryParams Directive and the Query Parameters Observable
- 解决 Jenkins 中无法展示 HTML 样式的问题,csp问题,Refused to apply inline style because it violates the following Content Security Policy directive: "style-src 'self'".
- ubuntu22.04安装deepin-wine报错:The following packages have unmet dependencies: libldap-2.4-2 : Depends:
- Unexpected XML declaration. The XML declaration must be the first node in the document and no white
- request for KPI tile number display could not be executed for the second time
- 解决The type or namespace name 'XXXX' does not exist in the namespace 'XXXXXXXXX' 的错误
- Pape之DL之CNN:2019《A Survey of the Recent Architectures of Deep Convolutional Neural Networks》翻译并解读第四章
- 魔戒 (The Lord of the Rings,又译《指环王》)
- The old instructions for getting the code
- ERROR 1290 (HY000): The MySQL server is running with the --secure-file-priv option so it cannot ···