小沙的中饭

小沙的中饭

// Problem: 小沙的中饭// Contest: NowCoder// URL: Memory Limit: 2 MB// Time Limit: 231178000 ms// 2022-02-15 23:23:06// // Powered by CP Editor (namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);i++)#define per(i,l,r) for(int i=(l);i>=(r);i--)#define ll long long#define pii pair#define mset(s,t) memset(s,t,sizeof(t))#define mcpy(s,t) memcpy(s,t,sizeof(t))#define fir first#define pb push_back#define sec second#define sortall(x) sort((x).begin(),(x).end())inline int read () { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch=='-'),ch= getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return f?-x:x;}template void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x/10); putchar(x % 10 + '0');}const int N = 1e3 + 10;void solve() { int n; int a[N]; ll f[N] = {0}; ll suf[N] = {0}; int cnt = 0; cin >> n; ll x = 0, y ; for (int i = 1; i<= n ;i++){ int t; cin >> t; if (t == 1) x ++; else { ++cnt; a[cnt] = t; } } sort(a +1, a + 1 + cnt); for (int i = cnt; i >= 1;i --) { suf[i] = suf[i + 1] + a[i]; f[i] = suf[i] - f[i + 1]; if (a[i] >= 4) f[i] = max (f[i], f[i + 1] + a[i] - 4); } x = suf[1] - f[1] + x, y = f[1]; if (x > y) puts("xiaohonwin"); else if (x == y) puts("loss"); else puts("xiaoshawin"); }int main () { int t; cin >> t; while (t --) solve(); return 0;}

首先需要明白一个关键性质，通过看一个环，我们可以发现对于小于4的我们一定拿不到，对于大于等于4的可以得到a[i] -4个至多 然后对于多个环我们需要用对于当前这个贪多少个需要考虑后面的，所以我们从大到小进行dp，这样就可以在知道后面的情况下对当前进行贪心。然后取max就行了

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。