个人练习11-17
11-17
- https://www.luogu.com.cn/problem/P2249
- https://www.luogu.com.cn/problem/P2240
- https://www.luogu.com.cn/problem/P1075
1 基本思路：
- 思路很简单，就是查找第一个满足条件的，我们只要用满足条件的不断去逼近左区间直至剩下最后一个满足的
答案一代码：
#include
using namespace std;
const int N = 1e6+10;
int n,q;
int a[N];
int solve(int s)
{int l = 1,r = n;while(l < r){int mid = (l+r)/2;if(a[mid] >= s) //满足条件的第一个,右区间不断往左挤r = mid ;else l = mid +1;}if(a[l] != s) return -1;return l;
}
int main()
{cin >> n >> q;for(int i = 1;i <= n;i ++)scanf("%d",&a[i]);while(q--){int x;scanf("%d",&x);int t = solve(x);printf("%d ",t);}
}
2 基本思路
- 很显然这是典型的贪心问题，那么我们只需要每次都是拿单价最高的物品就行了
- 代码
#include
using namespace std;const int N = 200;struct node
{int a,b;double c;
}s[N];int n,t;bool cmp(const node &a,const node &b)
{return a.c > b.c;
}
int main()
{scanf("%d%d",&n,&t);for(int i = 1;i <= n;i ++){int x,y;scanf("%d%d",&x,&y);s[i] = {x,y}; //直接集合赋值s[i].c = s[i].b*1.0/s[i].a;//存单价}// 贪心思想，我们总是选择单价最高的东西拿sort(s+1,s+n+1,cmp);double sum = 0.0;for(int i = 1;i <= n;i ++){if(t >= s[i].a) //是否还能全部装下{sum += s[i].b;t -= s[i].a;}else // 将就下,拿一部分{sum += s[i].c*t;break;}}printf("%.2lf\n",sum);
}
3 思路：
- 我们知道一个数由两个质因数表示，那么这两个
- 质因数分别位于[2,sqrt(n)] [sqrt(n),n/2]之间
- 那么思路就比较明确了可以使用试除法求小的(更容易找到)
代码：
#include
using namespace std;int main()
{int n;scanf("%d",&n);for(int i=2;i<=n/i;++i)if(n%i==0){printf("%d",n/i);return 0;}
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！