首页 > 代码库 > Codeforces 18D Seller Bob java大数+贪心
Codeforces 18D Seller Bob java大数+贪心
题目链接:点击打开链接
java:
import java.math.BigInteger; import java.util.Scanner; public class Main { static int N = 5005; static BigInteger[] er = new BigInteger[N]; static BigInteger E = new BigInteger("2"); static int[] a = new int[N]; static int[] mai = new int[N]; public static void main(String args[]) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); er[0] = BigInteger.valueOf(1); for (int i = 1; i < N; i++) er[i] = er[i - 1].multiply(E); for (int i = 0; i < n; i++) { String s = cin.next(); int now = cin.nextInt(); if (s.equals("sell") == true)now = -now-1; a[i] = now; mai[i] = -1; } for(int i = 0; i < n; i++) { int maxx = -1; for(int j = n-1;j >=0; j--) { if(mai[j]==-1 && a[j]<0) if(maxx==-1 || a[maxx]>a[j]) maxx = j; } if(maxx==-1)break; int find = -1; for(int j=maxx-1; j>=0; j--) { if(mai[j]==-1 && a[j]==(-a[maxx]-1)) {find = j; break;} else if(mai[j]==1) {find = -1;break;} } if(find==-1){mai[maxx]=0;continue;} for(int j=find;j<=maxx;j++)mai[j]=0; mai[maxx] = 1; } BigInteger ans = new BigInteger("0"); for (int i = 0; i < n; i++) if (mai[i] == 1) { ans = ans.add(er[-a[i]-1]); } System.out.println(ans); } }
C:
#include<stdio.h> #include<iostream> #include<string.h> #include<set> #include<vector> #include<map> #include<math.h> #include<queue> #include<string> #include<stdlib.h> #include<algorithm> using namespace std; #define N 5005 int er[N][N]; int ans[N]; void mul(int *y,int *x,int hehe) {//x = y*hehe; y[0] = 0; for(int i = 0; i < N; i++) { y[i] += x[i]*hehe; y[i+1] = y[i]/10; y[i] %= 10; } } void add(int *ans,int *x){//ans += x; for(int i = 0; i < N; i++) { ans[i] += x[i]; if(ans[i]>=10){ ans[i+1] += ans[i]/10; ans[i]%=10; } } } int a[N]; int mai[N]; int main(){ int i, j, n, now; memset(er[0], 0, sizeof er[0]); er[0][0] = 1; for(i=1;i<N;i++)mul(er[i], er[i-1], 2); while(~scanf("%d",&n)){ memset(mai, -1, sizeof mai); for(i=0;i<n;i++) { char s[10]; scanf("%s",s); scanf("%d",&now); if(s[0]=='s')now=-now-1; a[i] = now; } for(i=0;i<n;i++) { int maxx = -1; for(j=n-1;j>=0;j--) if(mai[j]==-1 && a[j]<0) if(maxx==-1 || a[maxx]>a[j]) maxx = j; if(maxx == -1)break; int find = -1; for(j=maxx-1; j>=0; j--) { if(mai[j]==-1 && a[j]==(-a[maxx]-1)) {find = j; break;} else if(mai[j]==1){find=-1;break;} } if(find==-1){mai[maxx] = 0;continue;} for(j=find;j<=maxx;j++)mai[j]=0; mai[maxx] = 1; } memset(ans, 0, sizeof ans); for(i = 0; i < n; i++) if(mai[i] == 1) add(ans, er[-a[i]-1]); int pos = N-1; while(ans[pos]==0)pos--; if(pos<0)pos=0; for(;pos>=0;pos--)printf("%d",ans[pos]); puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。