本文共 3750 字，大约阅读时间需要 12 分钟。
题目大意：一圈人围起来卖糖果，标号从1-n，每个位置的糖果都有自己的价格，一个人拿着钱从q开始走，能买则买，不能买则走到下一家，问最多能买多少件物品。
思路：此题的关键是不能买则走到下一家，一旦走到下一家，我们会发现之前的这家以后无论转几圈我们都买不起，所以直接把这个店删掉就可以了。
于是先将n当成周期，算出此时的sum，和原来的money比较，能买几个周期则买几个周期，然后遍历双向链表，不能买则删去，更新周期和sum，继续判断能不能买得起此时的周期，然后走到下一家店，直到剩下一家店。
由于每家店最多被删去一次，所以时间复杂度是O（n）的，只要注意链表的一些细节处理就可以了。
//#pragma comment(linker,"/STACK:102400000,102400000")#include #include #include #include #include #include #include #include #include #include #include //#include #define lson l,mid,rt<<1#define rson mid+1,r,(rt<<1)|1#define CLR(a,b) memset(a,b,sizeof(a))#define mkp(a,b) make_pair(a,b)typedef long long ll;using namespace std;inline ll read(){ ll x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}const int maxn=2e5+10;struct node{ ll val; int pre,Next;}a[maxn];ll sum,money,ans;int main(){ int n; cin>>n>>money; for(int i=1;i<=n;i++) { scanf("%lld",&a[i].val); sum+=a[i].val; a[i].pre=i-1,a[i].Next=i+1; } a[1].pre=n,a[n].Next=1; if(money>=sum) { ans+=money/sum*n; money%=sum; } int i=1; while(a[i].Next!=i) { if(money>=a[i].val) { ans++; money-=a[i].val; if(money<=0)break; i=a[i].Next; }else{ a[a[i].pre].Next=a[i].Next; a[a[i].Next].pre=a[i].pre; sum-=a[i].val; n--; if(money>=sum&&a[i].Next!=a[i].pre) { ans+=money/sum*n; money%=sum; } if(money<=0)break; i=a[i].Next; } } if(money>=sum) { ans+=money/sum*n; money%=sum; } printf("%lld\n",ans);}
XXI Berland Annual Fair is coming really soon! Traditionally fair consists of nn booths, arranged in a circle. The booths are numbered 11through nn clockwise with nn being adjacent to 11. The ii-th booths sells some candies for the price of aiai burles per item. Each booth has an unlimited supply of candies.
Polycarp has decided to spend at most TT burles at the fair. However, he has some plan in mind for his path across the booths:
Polycarp's money is finite, thus the process will end once he can no longer buy candy at any booth.
Calculate the number of candies Polycarp will buy.
The first line contains two integers nn and TT (1≤n≤2⋅1051≤n≤2⋅105, 1≤T≤10181≤T≤1018) — the number of booths at the fair and the initial amount of burles Polycarp has.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the price of the single candy at booth number ii.
Print a single integer — the total number of candies Polycarp will buy.
3 38 5 2 5
10
5 21 2 4 100 2 6
6
Let's consider the first example. Here are Polycarp's moves until he runs out of money:
No candy can be bought later. The total number of candies bought is 1010.
In the second example he has 11 burle left at the end of his path, no candy can be bought with this amount.
转载于:https://www.cnblogs.com/mountaink/p/9941089.html
