題干：
?

因為現(xiàn)在的新生太強了，都學(xué)會了“dp”，所以就有了這樣一個“dp”題，雙11時Gugugu有(x，x+1,x+2....y-1,y)元的抵用券無數(shù)張，但是Gugugu有強迫癥所以他希望他使用抵扣券正好能夠抵扣k元，這樣他就能安心的買下這件商品，但是他卻不會計算所以希望你們告訴他能不能一種方法使抵用券正好抵扣k元。

輸入描述:

?第一行輸入t代表有t組數(shù)據(jù)，第二行開始每行三個數(shù)k,x,y代表需要抵扣k元，x，y代表擁有抵用券的最小面值和最大面值。（1<=t<=200）（1<=k,x,y<109）(x<=y)

輸出描述:

輸出"Y"代表示能正好抵扣，輸出"N"代表不能正好抵扣

示例1

輸入

復(fù)制

2 7 2 4 6 4 5

輸出

復(fù)制

Y N

解題報告：

?

AC代碼：（一個AC代碼，但是不加那些剪枝會T）

#include<bits/stdc++.h> using namespace std; long long k,x,y; int main(){int T ;scanf("%d",&T);while(T--){scanf("%lld%lld%lld",&k,&x,&y);if(k<x) printf("N\n");else if(k>=x&&k<=y) printf("Y\n");else{int flag=0;for(int i=2;i<=10000000;i++){if(x*i<=k&&k<=y*i){printf("Y\n");flag=1;break;} }if(!flag)printf("N\n");}} }

AC代碼2：（這樣也可以500ms左右AC，其實可能是因為數(shù)據(jù)水了，我把枚舉上界改成1e4也AC了，等等好像1e3也AC了，確定是數(shù)據(jù)水了）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll k,x,y; int main() {int t;cin>>t;while(t--) {scanf("%lld%lld%lld",&k,&x,&y);int ff=0;for(ll i = 1; i<=(ll)1e7; i++) {if(i*x <=k && i*y >=k) {ff=1;puts("Y");break;}}if(ff==0) puts("N");}return 0 ;}

正解：

#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PI; const int maxn = 1e5+5; const ULL mod = 1e9+7; const LL inf = 1e18; int main() {int T; scanf( "%d", &T );while( T-- ){int k,x,y; scanf( "%d%d%d", &k, &x, &y );if( k<x ) printf( "N\n" );else if( k>=x&&k<=y||k%x==0 ) printf( "Y\n" );else{int pp = k/x;int p = k%x;if( p%pp==0 ) p /= pp;else p = p/pp+1;if( p<=y-x ) printf( "Y\n" );else printf( "N\n" );}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 289K】这是一个沙雕题III（贪心，思维枚举，技巧trick，计算上下界）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。