首页 > 代码库 > zoj 3672 思维题
zoj 3672 思维题
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4915
真是老了,脑子不会动了,但是其实就算现在搜了题解A了,还是没总结出思维方式
三点:
1、segma(a[i]-b[i])必须是偶数,,因为其实每次操作都是相当于从segma(a[i]-b[i])里面减去2*delta
2、a[i]>=b[i] 题目说的很清楚,只能减去,所以这点必须满足
前两点都想到了,但是自己能举出反例,后来队友A掉了
3、max(a[i]-b[i]) * 2 <= segma(a[i]-b[i]) 否则的话,最大的肯定消不掉
但是其实还是没有总结出思维方法,我一直做的都是,自己从小的例子枚举,找方法,然后推广至大的,但是好像不行这次
可能需要从反例里面多总结规律,然后如果自己反例都想出来都能应对,应该就对了
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <iomanip> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdout) const ll ll_INF = ((ull)(-1))>>1; const double EPS = 1e-8; const int INF = 100000000; const int MAXN = 10000+100; ll a[MAXN],b[MAXN]; ll vis[MAXN]; int n; int main() { while(~scanf("%d",&n)) { CL(vis,0); int flag=1; ll mmax=0,ret=0; for(int i=0;i<n;i++) { scanf("%lld%lld",&a[i],&b[i]); if(a[i]<b[i])flag=0; if(a[i]>=b[i])vis[i]=a[i]-b[i]; mmax=max(vis[i],mmax); ret+=vis[i]; } if(flag==0 || 2*mmax >ret || ret%2) printf("NO\n"); else printf("YES\n"); } return 0; }
zoj 3672 思维题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。